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.
1import java.util.HashMap;
2import java.util.Map;
3
4public class LongestGoodSubarray {
5 public static int longestGoodSubarray(int[] nums, int k) {
6 Map<Integer, Integer> freq = new HashMap<>();
7 int start = 0, max_len = 0;
8
9 for (int end = 0; end < nums.length; end++) {
10 freq.put(nums[end], freq.getOrDefault(nums[end], 0) + 1);
11 while (freq.get(nums[end]) > k) {
12 freq.put(nums[start], freq.get(nums[start]) - 1);
13 if (freq.get(nums[start]) == 0) {
14 freq.remove(nums[start]);
15 }
16 start++;
17 }
18 max_len = Math.max(max_len, end - start + 1);
19 }
20
21 return max_len;
22 }
23
24 public static void main(String[] args) {
25 int[] nums = {1, 2, 3, 1, 2, 3, 1, 2};
26 int k = 2;
27 System.out.println(longestGoodSubarray(nums, k));
28 }
29}This Java implementation employs a HashMap to track frequencies of elements within the window. The loop traverses through nums, maintaining a valid window such that no frequency exceeds k. max_len is updated to ensure we capture the longest subarray satisfying the conditions.
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.