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.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
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.
Example 2:
Input: nums = [1,2,1,2,1,2,1,2], k = 1 Output: 2 Explanation: The longest possible good subarray is [1,2] since the values 1 and 2 occur at most once in this subarray. Note that the subarray [2,1] is also good. It can be shown that there are no good subarrays with length more than 2.
Example 3:
Input: nums = [5,5,5,5,5,5,5], k = 4 Output: 4 Explanation: The longest possible good subarray is [5,5,5,5] since the value 5 occurs 4 times in this subarray. It can be shown that there are no good subarrays with length more than 4.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= nums.lengthUse a sliding window technique to find the longest subarray that satisfies the condition where no element occurs more than k times. You can maintain a frequency map that tracks the count of each element in the current window.
This C solution uses a sliding window over the array nums. The frequency of each element in the window is stored in an array frequency. The window [start, end] is adjusted to keep all frequencies not exceeding k. We resize our window by incrementing start when an element's frequency exceeds k.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the number of elements in nums, as each index is visited at most twice.
Space Complexity: O(m), where m is the maximum element value in nums representing the size of the frequency array.
A different approach is to use binary search to determine the maximum subarray length. The problem translates to searching for the maximum length for which a good subarray exists, using a helper function that verifies subarray validity in O(n) time.
This C approach involves a binary search to deduce the maximum length of a subarray fulfilling the condition, making use of a helper function. The helper function checks if there exists a good subarray of that length, leveraging frequency arrays similarly to a sliding window.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to the binary search layers and inner check iteration.
Space Complexity: O(m) for the frequency array, where m is the maximum element value.
| Approach | Complexity |
|---|---|
| Sliding Window with Frequency Map | Time Complexity: |
| Binary Search Over Subarray Length | Time Complexity: |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,285 views views
Watch 9 more video solutions →Practice Length of Longest Subarray With at Most K Frequency with our built-in code editor and test cases.
Practice on FleetCode