Problem

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 thelongest good subarray of nums .

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

Examples

Example 1

1
2
3
4
5
6
7
8


    
    
    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

1
2
3
4
5
6
7
8


    
    
    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

1
2
3
4
5
6
7
8


    
    
    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^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= nums.length

Solution

Method 1 – Sliding Window with Hash Map

Intuition

To find the longest subarray where no element appears more than k times, we can use a sliding window. We expand the window to the right, and if any element’s frequency exceeds k, we shrink the window from the left until all frequencies are at most k.

Approach

  1. Use two pointers l and r to represent the window.
  2. Use a hash map to count the frequency of each element in the window.
  3. For each r, add nums[r] to the window and update its frequency.
  4. If any frequency exceeds k, move l right and decrease frequencies until all are at most k.
  5. Track the maximum window size.
  6. Return the maximum size found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

func maxSubarrayLength(nums []int, k int) int {
    freq := map[int]int{}
    l, ans := 0, 0
    for r, x := range nums {
        freq[x]++
        for freq[x] > k {
            freq[nums[l]]--
            l++
        }
        if r-l+1 > ans { ans = r-l+1 }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        int l = 0, ans = 0;
        for (int r = 0; r < nums.length; r++) {
            freq.put(nums[r], freq.getOrDefault(nums[r], 0) + 1);
            while (freq.get(nums[r]) > k) {
                freq.put(nums[l], freq.get(nums[l]) - 1);
                l++;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun maxSubarrayLength(nums: IntArray, k: Int): Int {
        val freq = mutableMapOf<Int, Int>()
        var l = 0
        var ans = 0
        for (r in nums.indices) {
            freq[nums[r]] = freq.getOrDefault(nums[r], 0) + 1
            while (freq[nums[r]]!! > k) {
                freq[nums[l]] = freq[nums[l]]!! - 1
                l++
            }
            ans = maxOf(ans, r - l + 1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def maxSubarrayLength(self, nums: list[int], k: int) -> int:
        from collections import defaultdict
        freq = defaultdict(int)
        l = ans = 0
        for r, x in enumerate(nums):
            freq[x] += 1
            while freq[x] > k:
                freq[nums[l]] -= 1
                l += 1
            ans = max(ans, r - l + 1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn max_subarray_length(nums: Vec<i32>, k: i32) -> i32 {
        use std::collections::HashMap;
        let mut freq = HashMap::new();
        let (mut l, mut ans) = (0, 0);
        for (r, &x) in nums.iter().enumerate() {
            *freq.entry(x).or_insert(0) += 1;
            while freq[&x] > k {
                *freq.get_mut(&nums[l]).unwrap() -= 1;
                l += 1;
            }
            ans = ans.max(r as i32 - l as i32 + 1);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    maxSubarrayLength(nums: number[], k: number): number {
        const freq = new Map<number, number>();
        let l = 0, ans = 0;
        for (let r = 0; r < nums.length; r++) {
            freq.set(nums[r], (freq.get(nums[r]) ?? 0) + 1);
            while ((freq.get(nums[r]) ?? 0) > k) {
                freq.set(nums[l], (freq.get(nums[l]) ?? 0) - 1);
                l++;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. Each element is processed at most twice.
  • 🧺 Space complexity: O(m), where m is the number of unique elements in nums (for the frequency map).