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
đź‘‹ While you are here

Reinvent your career. Join DEV.

It takes one minute and is worth it for your career.

Get started

Top comments (0)

đź‘‹ Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay