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.
This C solution uses a sliding window over the array nums. The frequency of each element in the window is stored in an array frequency. The window [start, end] is adjusted to keep all frequencies not exceeding k. We resize our window by incrementing start when an element's frequency exceeds k.
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.
1#include <iostream>
2#include <unordered_map>
3#include <vector>
4using namespace std;
5
6bool isGoodSubarray(vector<int>& nums, int subarraySize, int k) {
7 unordered_map<int, int> freq;
8 for (int i = 0; i < subarraySize; i++) {
9 freq[nums[i]]++;
10 if (freq[nums[i]] > k) return false;
11 }
12 for (int i = subarraySize; i < nums.size(); i++) {
13 freq[nums[i]]++;
14 if (freq[nums[i]] > k) return false;
15 freq[nums[i - subarraySize]]--;
16 if (freq[nums[i - subarraySize]] == 0) {
17 freq.erase(nums[i - subarraySize]);
18 }
19 }
20 return true;
21}
22
23int longestGoodSubarray(vector<int>& nums, int k) {
24 int low = 1, high = nums.size(), answer = 0;
25
26 while (low <= high) {
27 int mid = low + (high - low) / 2;
28 if (isGoodSubarray(nums, mid, k)) {
29 answer = mid;
30 low = mid + 1;
31 } else {
32 high = mid - 1;
33 }
34 }
35
36 return answer;
37}
38
39int main() {
40 vector<int> nums = {1, 2, 3, 1, 2, 3, 1, 2};
41 int k = 2;
42 cout << longestGoodSubarray(nums, k) << endl;
43 return 0;
44}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.