Q57 Arithmetic Slices II - Subsequence - LeetCode 446
Sat Apr 01 2023 13:34:09 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int numberOfArithmeticSlices(int[] nums) {
/* Q57 of dp playlist , every cell denotes total no. of subarrays APs
of size >=2 ending at that ith element. here dp is an array of HM
we make a HM[] to store common difference -> no.of Ap for all elements
*/
int n = nums.length , ans = 0;
//making HM
HashMap<Integer,Integer>[] map = new HashMap[n];
//iniitalizing all hashmap in hashmap[]
for(int i = 0 ; i < n ; i++)
map[i] = new HashMap<>();
//common approach of LIS
for(int i = 1 ; i < n ;i++){
for(int j = i-1 ; j >= 0 ; j--){
long cd = (long)nums[i]-(long)nums[j];
//edge case if cd goes out of integer range
if(cd <= Integer.MIN_VALUE || cd >= Integer.MAX_VALUE)continue;
/*we traverse the array in LIS fashion to store subarray ap of size >=2
for each element if at any moment we find that the common difference
found by nums[i] - nums[j] already exists that means current element
is going to be the 3rd or more member of the AP so now total no. of
AP's of length >=3 increases by 1 and we add to the answer */
if(map[j].containsKey((int)cd)){
int AP = map[j].get((int)cd);
map[i].put((int)cd , map[i].getOrDefault((int)cd,0) + AP+1);
ans += AP;
}
/* if its a new (cd then we just add it to the map and they become a 2
sized ap , if in the future some number has same common difference it
will add to this AP
*/
else
map[i].put((int)cd , map[i].getOrDefault((int)cd,0)+1);
}
}
return ans;
}
}
content_copyCOPY
https://leetcode.com/problems/arithmetic-slices-ii-subsequence/description/
Comments