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 <stdio.h>
2#include <stdlib.h>
3
4int longestGoodSubarray(int* nums, int numsSize, int k) {
5 int start = 0, max_len = 0;
6 int* frequency = (int*)calloc(1000000001, sizeof(int));
7 int distinct = 0;
8
9 for (int end = 0; end < numsSize; end++) {
10 frequency[nums[end]]++;
11 if (frequency[nums[end]] == 1) {
12 distinct++;
13 }
14
15 while (frequency[nums[end]] > k) {
16 frequency[nums[start]]--;
17 if (frequency[nums[start]] == 0) {
18 distinct--;
19 }
20 start++;
21 }
22
23 if (frequency[nums[end]] <= k) {
24 max_len = (end - start + 1) > max_len ? (end - start + 1) : max_len;
25 }
26 }
27
28 free(frequency);
29 return max_len;
30}
31
32int main() {
33 int nums[] = {1, 2, 3, 1, 2, 3, 1, 2};
34 int k = 2;
35 int length = longestGoodSubarray(nums, 8, k);
36 printf("%d\n", length);
37 return 0;
38}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.
using System.Collections.Generic;
class Program {
public static bool IsGoodSubarray(int[] nums, int subarraySize, int k) {
Dictionary<int, int> freq = new Dictionary<int, int>();
for (int i = 0; i < subarraySize; i++) {
if (!freq.ContainsKey(nums[i])) freq[nums[i]] = 0;
freq[nums[i]]++;
if (freq[nums[i]] > k) return false;
}
for (int i = subarraySize; i < nums.Length; i++) {
if (!freq.ContainsKey(nums[i])) freq[nums[i]] = 0;
freq[nums[i]]++;
if (freq[nums[i]] > k) return false;
freq[nums[i - subarraySize]]--;
if (freq[nums[i - subarraySize]] == 0) freq.Remove(nums[i - subarraySize]);
}
return true;
}
public static int LongestGoodSubarray(int[] nums, int k) {
int low = 1, high = nums.Length, 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;
}
static void Main() {
int[] nums = {1, 2, 3, 1, 2, 3, 1, 2};
int k = 2;
Console.WriteLine(LongestGoodSubarray(nums, k));
}
}This C# program deploys a binary search to pinpoint the longest subarray satisfying the condition. The determination of subarray validity at each candidate length is done through a secondary helper function, which validates the current window behavior.