This is a fixed size SlidingWindow
Problem
TC: O(n*100) = O(n)
SC:O(n) for using HashMap for storing the frequency of nums[i]
class Solution {
public int[] getSubarrayBeauty(int[] nums, int k, int x) {
Map<Integer,Integer> map = new HashMap<>();
int left =0,right = 0;
int index = 0;
int arr[] = new int[nums.length-k+1];
while(right<nums.length){
// keep frequency count of each no. in the nums
map.put(nums[right],map.getOrDefault(nums[right],0)+1);
if(right-left +1 >k){//if any time window size become more than k, remove decrease frequency of nums[left] from the map and increment left pointer
int c = map.get(nums[left]);
if(c ==1) map.remove(nums[left]); // if c ==1 then c-- = 0, remove that no. from the map
else{
map.put(nums[left],c-1);// else decrease the frequency by 1
}
left++;
}
if(right-left +1 ==k){// if we have reached the window size find the xth smallest negative no. else put 0 for this window
int count =0;
for(int i =-50;i<=50;i++){// since the values in the nums are between -50 to + 50
if(map.containsKey(i)){// -50,-49,-48,-47.......+50 ( we are checking till we find the xth smallest)
count+=map.get(i);// if the a number say -N comes 2 times then we increment the counter by 2
if(count >= x){// at any point if count is = x or greater than x then we have found the xth smallest value in the array
//if the xth smallest number is non negative consider 0 in this case else i(as i is the xth smallest the window of size k)
if(i<0){arr[index++] = i;}
else arr[index++] = 0;
break;
}
}
}
}
right++;
}
return arr;
}
}
Top comments (0)