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.
JavaScript solution adopts a binary search approach to determine the maximum length of a good subarray. A helper function is employed for validating subarray quality by evaluating element frequencies within the selected window size.