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)
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:
Finally, return the maximum length discovered.
Complexity: