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.
1#include <iostream>
2#include <unordered_map>
3#include <vector>
4using namespace std;
5
6int longestGoodSubarray(vector<int>& nums, int k) {
7 unordered_map<int, int> freq;
8 int start = 0, max_len = 0;
9
10 for (int end = 0; end < nums.size(); ++end) {
11 freq[nums[end]]++;
12 while (freq[nums[end]] > k) {
13 freq[nums[start]]--;
14 if (freq[nums[start]] == 0) {
15 freq.erase(nums[start]);
16 }
17 start++;
18 }
19 max_len = max(max_len, end - start + 1);
20 }
21
22 return max_len;
23}
24
25int main() {
26 vector<int> nums = {1, 2, 3, 1, 2, 3, 1, 2};
27 int k = 2;
28 cout << longestGoodSubarray(nums, k) << endl;
29 return 0;
30}The C++ approach uses an unordered_map to store the frequency of elements in the current window. The algorithm iterates through nums, adjusting the window to ensure no element's frequency exceeds k. As we progress, we update max_len to the maximum length of any valid subarray found.
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.