Sliding Window : 5 (+HashMap)

Day 4/75:

Question: Length of Longest Subarray With at Most K Frequency -(Medium)

You are given an integer array nums and an integer k.

The frequency of an element x is the number of times it occurs in an array.

An array is called good if the frequency of each element in this array is less than or equal to k.

Return the length of the longest good subarray of nums.

Input: nums = [1,2,3,1,2,3,1,2], k = 2
Output: 6
Explanation: The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good.
It can be shown that there are no good subarrays with length more than 6.        

========== Please Feel free to Jump to Actual Approach============= Intuition: Initially, I considered obtaining the frequency of each element and determining the count of elements based on Min(k, map.get(nums[i])). Subsequently, I intended to add the keys to the answer list for (count) number of times and return the size of the list, assuming a straightforward approach. However, I missed the requirement for identifying the longest contiguous subarray where all elements have frequencies less than or equal to k.

Approach : ( Which doesn't work fully)

1. You initialize a list list to store the elements of the longest good subarray.
2. You initialize a HashMap map to store the frequency of each element in the input array.
3. You iterate through the input array nums, updating the frequencies in the map.
4. Then, you iterate through the keys of the map (unique elements in nums), and for each key, you determine the count as the minimum of k and the frequency of that element. You then add that key to the list count times.
5. Finally, return size of list.

Code:

==================================================

Actual Approach: Best and Easy (SlidingWindow+HashMap)

Inuition:

By little more thinking, my instinct led me to consider same sliding window. Given that our objective is to identify the longest subarray adhering to a specific condition. Since the task is finding the longest subarray where each element's frequency remains within the threshold of k, employing a sliding window allows us to efficiently monitor the frequency of elements within a subarray as it dynamically adjusts.

Approach:

1. Initialize two pointers, start and end, marking the boundaries of window.
2. HashMap to store the frequency of elements within the current subarray.
3. Traverse through the array from left to right, incrementing the end pointer. Update the frequency of nums[end] in the map.
4. If the frequency of nums[end] > k, shrink the window from the start until the frequency of the newly inserted element decreases by one.
5. Continuously update the maximum length of the good subarray, if necessary.

Finally, return the maximum length discovered.

Complexity:

• Time complexity: O(n)
• Space complexity: O(n)