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.
1def longest_good_subarray(nums, k):
2 from collections import defaultdict
3 freq = defaultdict(int)
4 start = 0
5 max_len = 0
6
7 for end in range(len(nums)):
8 freq[nums[end]] += 1
9 while freq[nums[end]] > k:
10 freq[nums[start]] -= 1
11 if freq[nums[start]] == 0:
12 del freq[nums[start]]
13 start += 1
14 max_len = max(max_len, end - start + 1)
15 return max_len
16
17# Example usage
18nums = [1, 2, 3, 1, 2, 3, 1, 2]
19k = 2
20print(longest_good_subarray(nums, k))Using a Python defaultdict to manage element frequencies, this implementation applies the sliding window technique similarly. The start and end pointers are adjusted accordingly, and the maximum valid subarray length is recorded.
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.
This Java solution executes a binary search across potential subarray lengths to deduce the maximum viable length. The subarray evaluation is achieved through the isGoodSubarray helper function, iterating the array and manipulating frequencies to stay within set constraints.