DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Sliding subarray beauty

This is a fixed size SlidingWindow Problem

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)