Length of Longest Subarray With at Most K Frequency

Med

#2638Time: O(N^2), where N is the number of elements in `nums`. The two nested loops lead to a quadratic number of operations. For each pair of `(i, j)`, the operations inside the inner loop are constant time on average (for HashMap).Space: O(U) or O(N) in the worst case, where U is the number of unique elements in the subarray `nums[i...j]`. In the worst case, all elements are unique, so the space required for the `frequencyMap` can be up to O(N).2 companies

Patterns

Sliding Window

Data structures

Array Hash Table

Companies

MakeMyTrip Citadel

Prompt

You are given an integer array nums and an integer k.

The frequency of an element x is the number of times it occurs in an array.

An array is called good if the frequency of each element in this array is less than or equal to k.

Return the length of the longest good subarray of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,3,1,2,3,1,2], k = 2
Output: 6
Explanation: The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good.
It can be shown that there are no good subarrays with length more than 6.

Example 2:

Input: nums = [1,2,1,2,1,2,1,2], k = 1
Output: 2
Explanation: The longest possible good subarray is [1,2] since the values 1 and 2 occur at most once in this subarray. Note that the subarray [2,1] is also good.
It can be shown that there are no good subarrays with length more than 2.

Example 3:

Input: nums = [5,5,5,5,5,5,5], k = 4
Output: 4
Explanation: The longest possible good subarray is [5,5,5,5] since the value 5 occurs 4 times in this subarray.
It can be shown that there are no good subarrays with length more than 4.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= nums.length

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible subarray to see if it's a "good" subarray. A good subarray is one where the frequency of each element is at most k. We iterate through all possible start points of a subarray and, for each start point, extend the subarray to the right, checking its validity at each step.

Algorithm

Initialize maxLength = 0.
Iterate through the array with an index i from 0 to n-1 to select the start of the subarray.
For each i, create a new frequency map.
Iterate with an index j from i to n-1 to select the end of the subarray.
In the inner loop, add nums[j] to the current subarray and update its frequency in the map.
Check if the frequency of nums[j] is greater than k.
If it is, the subarray nums[i...j] is invalid. Break the inner loop and try the next starting position i+1.
If it's not, the subarray is valid. Update maxLength = max(maxLength, j - i + 1).
After all subarrays are checked, return maxLength.

Walkthrough

We use two nested loops to generate all subarrays. The outer loop, with index i, determines the starting point of the subarray. The inner loop, with index j, determines the ending point.

For each starting point i, we initialize a frequency map. As we extend the subarray by incrementing j, we update the frequency of the new element nums[j] in the map.

After updating, we check if the frequency of nums[j] exceeds k.

If it does, the current subarray nums[i...j] is not good. Since any further extension of this subarray (by increasing j) will also include this violation, it will also not be good. Therefore, we can break the inner loop and move to the next starting point i+1.

If the frequency does not exceed k, the subarray nums[i...j] is good. We then update our maximum length found so far with the length of this current subarray, which is j - i + 1.

This process is repeated for all possible starting positions.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int maxSubarrayLength(int[] nums, int k) {6        int n = nums.length;7        int maxLength = 0;8 9        if (n == 0) {10            return 0;11        }12 13        for (int i = 0; i < n; i++) {14            Map<Integer, Integer> frequencyMap = new HashMap<>();15            for (int j = i; j < n; j++) {16                int currentNum = nums[j];17                frequencyMap.put(currentNum, frequencyMap.getOrDefault(currentNum, 0) + 1);18 19                if (frequencyMap.get(currentNum) > k) {20                    break; // This subarray and any longer ones starting at i are invalid21                }22                maxLength = Math.max(maxLength, j - i + 1);23            }24        }25        return maxLength;26    }27}

Complexity

Time

O(N^2), where N is the number of elements in `nums`. The two nested loops lead to a quadratic number of operations. For each pair of `(i, j)`, the operations inside the inner loop are constant time on average (for HashMap).

Space

O(U) or O(N) in the worst case, where U is the number of unique elements in the subarray `nums[i...j]`. In the worst case, all elements are unique, so the space required for the `frequencyMap` can be up to O(N).

Trade-offs

Pros

Simple to understand and implement.
It's a direct translation of the problem statement.

Cons

Inefficient for large inputs due to its quadratic time complexity.
It will likely result in a "Time Limit Exceeded" (TLE) error on platforms with large test cases.
Redundant computations: The frequency map is rebuilt for each starting position i, recalculating frequencies for overlapping parts of subarrays.

This approach uses a sliding window, defined by two pointers start and end, to efficiently find the longest "good" subarray. We expand the window by moving the end pointer and shrink it by moving the start pointer whenever the subarray within the window becomes "bad" (i.e., an element's frequency exceeds k).

Algorithm

Initialize a start pointer to 0, maxLength to 0, and a frequency map.
Iterate through the array with an end pointer from 0 to n-1.
For each element nums[end], increment its count in the frequency map.
Check if the frequency of nums[end] has exceeded k.
If it has, shrink the window from the left: repeatedly decrement the frequency of nums[start] and increment start until the window is valid again.
After each potential expansion and necessary contraction, the window nums[start...end] is a valid "good" subarray. Update maxLength with the current window's size (end - start + 1).
After the loop finishes, return maxLength.

Walkthrough

We maintain a window nums[start...end] and a frequency map for the elements within this window.

We iterate through the array with the end pointer, from left to right, to expand the window.

In each step, we add nums[end] to our window and update its frequency in the map.

After adding nums[end], we check if its frequency has exceeded k.

If frequencyMap.get(nums[end]) > k, the window is no longer "good". We must shrink the window from the left by incrementing the start pointer until the window becomes "good" again. This involves decrementing the frequency of nums[start] in our map and then moving start one position to the right. We repeat this shrinking process until the condition that caused the violation is resolved.

At each step, after ensuring the window nums[start...end] is "good", we calculate its length (end - start + 1) and update our maxLength if the current length is greater.

This way, both start and end pointers only move forward, ensuring each element is processed a constant number of times.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int maxSubarrayLength(int[] nums, int k) {6        int n = nums.length;7        int maxLength = 0;8        int start = 0;9        Map<Integer, Integer> frequencyMap = new HashMap<>();10 11        for (int end = 0; end < n; end++) {12            int endNum = nums[end];13            frequencyMap.put(endNum, frequencyMap.getOrDefault(endNum, 0) + 1);14 15            // Shrink the window from the left if the frequency of any element exceeds k16            while (frequencyMap.get(endNum) > k) {17                int startNum = nums[start];18                frequencyMap.put(startNum, frequencyMap.get(startNum) - 1);19                start++;20            }21 22            // Update the maximum length found so far23            maxLength = Math.max(maxLength, end - start + 1);24        }25 26        return maxLength;27    }28}

Complexity

Time

O(N), where N is the number of elements in `nums`. Both the `start` and `end` pointers traverse the array at most once, so each element is visited a constant number of times.

Space

O(U) or O(N) in the worst case, where U is the number of unique elements in `nums`. The space is used for the `frequencyMap` to store the counts of elements in the current window.

Trade-offs

Pros

Highly efficient with a linear time complexity.
Optimal solution for this problem, passing even for large inputs.
Processes each element a constant number of times.

Cons

Slightly more complex to reason about and implement compared to the brute-force approach.
Requires extra space for the frequency map.

Solutions

Solution

1class Solution {2public3  int maxSubarrayLength(int[] nums, int k) {4    Map<Integer, Integer> cnt = new HashMap<>();5    int ans = 0;6    for (int i = 0, j = 0; i < nums.length; ++i) {7      cnt.merge(nums[i], 1, Integer : : sum);8      while (cnt.get(nums[i]) > k) {9        cnt.merge(nums[j++], -1, Integer : : sum);10      }11      ans = Math.max(ans, i - j + 1);12    }13    return ans;14  }15}

1class Solution {2public:3  int maxSubarrayLength(vector<int> &nums, int k) {4    unordered_map<int, int> cnt;5    int ans = 0;6    for (int i = 0, j = 0; i < nums.size(); ++i) {7      ++cnt[nums[i]];8      while (cnt[nums[i]] > k) {9        --cnt[nums[j++]];10      }11      ans = max(ans, i - j + 1);12    }13    return ans;14  }15};

1class Solution:2    def maxSubarrayLength(self, nums: List[int], k: int) -> int: cnt = defaultdict(int) ans = j = 0 for i, x in enumerate(nums): cnt[x] += 1 while cnt[x] > k: cnt[nums[j]] -= 1 j += 1 ans = max(ans, i - j + 1) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem