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.
1using System;
2using System.Collections.Generic;
3
4class Program {
5 public static int LongestGoodSubarray(int[] nums, int k) {
6 Dictionary<int, int> freq = new Dictionary<int, int>();
7 int start = 0, max_len = 0;
8
9 for (int end = 0; end < nums.Length; end++) {
10 if (freq.ContainsKey(nums[end]))
11 freq[nums[end]]++;
12 else
13 freq[nums[end]] = 1;
14
15 while (freq[nums[end]] > k) {
16 freq[nums[start]]--;
17 if (freq[nums[start]] == 0)
18 freq.Remove(nums[start]);
19 start++;
20 }
21
22 max_len = Math.Max(max_len, end - start + 1);
23 }
24
25 return max_len;
26 }
27
28 static void Main() {
29 int[] nums = {1, 2, 3, 1, 2, 3, 1, 2};
30 int k = 2;
31 Console.WriteLine(LongestGoodSubarray(nums, k));
32 }
33}This C# program utilizes a Dictionary to control the sliding window mechanism by tracking frequencies within the current window. The approach remains similar by adjusting pointers to maintain the window validity and updating the maximum length.
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.