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.
#include <unordered_map>
#include <vector>
using namespace std;
bool isGoodSubarray(vector<int>& nums, int subarraySize, int k) {
unordered_map<int, int> freq;
for (int i = 0; i < subarraySize; i++) {
freq[nums[i]]++;
if (freq[nums[i]] > k) return false;
}
for (int i = subarraySize; i < nums.size(); i++) {
freq[nums[i]]++;
if (freq[nums[i]] > k) return false;
freq[nums[i - subarraySize]]--;
if (freq[nums[i - subarraySize]] == 0) {
freq.erase(nums[i - subarraySize]);
}
}
return true;
}
int longestGoodSubarray(vector<int>& nums, int k) {
int low = 1, high = nums.size(), answer = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isGoodSubarray(nums, mid, k)) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
int main() {
vector<int> nums = {1, 2, 3, 1, 2, 3, 1, 2};
int k = 2;
cout << longestGoodSubarray(nums, k) << endl;
return 0;
}In C++, this method featuring binary search to find the optimal subarray size leverages a helper function. The helper function sweeps the array to evaluate potential subarrays while adjusting for frequency changes at each end of the window, restoring balance as needed.