Q-14 PepCoding | Equivalent Subarrays
Wed Jan 25 2023 06:18:06 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution
{
// Method to calculate distinct sub-array
static int countDistinctSubarray(int arr[], int n)
{
//similiar to previous question
//finding total unique numbers
HashSet<Integer> set = new HashSet<>();
for(int val : arr)
set.add(val);
int k = set.size();
//exactly k strings = atmost(k) - atmost(k-1)
return atmostK(arr , k) - atmostK(arr,k-1);
}
//finding atmost(k) strings
static int atmostK(int arr[] , int k){
int ans = 0;
int j = 0;
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0 ;i < arr.length ; i++){
int val = arr[i];
map.put(val , map.getOrDefault(val,0)+1);
while(map.size() > k){
int temp = arr[j];
if(map.get(temp) == 1)
map.remove(temp);
else
map.put(temp , map.get(temp)-1);
j++;
}
//adding all subtrings
ans += i-j+1;
}
return ans;
}
}
content_copyCOPY
https://www.pepcoding.com/resources/data-structures-and-algorithms-in-java-levelup/hashmap-and-heaps/equivalent-subarrays-official/ojquestion
Comments