Sponsored
Sponsored
Use 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.
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.
1function longestGoodSubarray(nums, k) {
2 let freq = new Map();
3 let start = 0, max_len = 0;
4
5 for (let end = 0; end < nums.length; end++) {
6 freq.set(nums[end], (freq.get(nums[end]) || 0) + 1);
7
8 while (freq.get(nums[end]) > k) {
9 freq.set(nums[start], freq.get(nums[start]) - 1);
10 if (freq.get(nums[start]) === 0) {
11 freq.delete(nums[start]);
12 }
13 start++;
14 }
15
16 max_len = Math.max(max_len, end - start + 1);
17 }
18
19 return max_len;
20}
21
22const nums = [1, 2, 3, 1, 2, 3, 1, 2];
23const k = 2;
24console.log(longestGoodSubarray(nums, k));This JavaScript function uses a Map to maintain element frequencies during window traversal. The sliding window approach is employed by dynamically adjusting the start pointer and measuring the maximum valid subarray length concurrently.
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.
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.
In Python, the function employs binary search to explore the potential maximum subarray length. For each candidate length, the validity of the subarray is determined by a helper function that reviews the current sliding window setup using defaultdict for frequencies.