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.
This Java solution executes a binary search across potential subarray lengths to deduce the maximum viable length. The subarray evaluation is achieved through the isGoodSubarray helper function, iterating the array and manipulating frequencies to stay within set constraints.