2958. Length of Longest Subarray With at Most K Frequency - Explanation

Description

Return the length of the longest contiguous subarray of nums in which every distinct value occurs at most k times. The limit applies separately to each value.

Example 1:

Input: nums = [1,2,1,2,3]
k = 1

Output: 3

Explanation: The final three values [1,2,3] are all distinct and form a valid subarray of length 3. Every longer subarray repeats a value, which exceeds k = 1.

Example 2:

Input: nums = [4,4,4]
k = 2

Output: 2

Explanation: Any two adjacent values form a valid subarray. All three together would contain three copies of 4, so the maximum length is 2.

Example 3:

Input: nums = [2,3,2]
k = 3

Output: 3

Explanation: No value in the full array occurs more than three times, so all three elements can be kept.

Constraints:

1 <= nums.length <= 100000
1 <= nums[i] <= 1000000000
1 <= k <= nums.length

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sliding Window Technique - Maintaining a dynamic window with two pointers that expands and contracts based on constraints
Hash Maps - Tracking element frequencies within the current window efficiently
Frequency Counting - Incrementing and decrementing counts as elements enter and leave the window

1. Brute Force

Intuition

The most direct approach is to examine every possible subarray and check if it satisfies the frequency constraint. For each starting position, we extend the subarray one element at a time, tracking element frequencies as we go. The moment any element appears more than k times, we stop extending and move to the next starting position.

Algorithm

Initialize res to track the maximum valid subarray length.
For each starting index i, create a frequency map and iterate through all ending indices j.
Increment the count for each element as we expand the window.
If any element's frequency exceeds k, break out of the inner loop.
Otherwise, update res with the current subarray length j - i + 1.
Return res after checking all subarrays.

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        n, res = len(nums), 0

        for i in range(n):
            count = defaultdict(int)
            for j in range(i, n):
                count[nums[j]] += 1
                if count[nums[j]] > k:
                    break
                res = max(res, j - i + 1)

        return res

public class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        int n = nums.length, res = 0;

        for (int i = 0; i < n; i++) {
            Map<Integer, Integer> count = new HashMap<>();
            for (int j = i; j < n; j++) {
                count.put(nums[j], count.getOrDefault(nums[j], 0) + 1);
                if (count.get(nums[j]) > k) {
                    break;
                }
                res = Math.max(res, j - i + 1);
            }
        }
        return res;
    }
}

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        int n = nums.size(), res = 0;

        for (int i = 0; i < n; i++) {
            unordered_map<int, int> count;
            for (int j = i; j < n; j++) {
                count[nums[j]]++;
                if (count[nums[j]] > k) {
                    break;
                }
                res = max(res, j - i + 1);
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    maxSubarrayLength(nums, k) {
        let n = nums.length,
            res = 0;

        for (let i = 0; i < n; i++) {
            let count = new Map();
            for (let j = i; j < n; j++) {
                count.set(nums[j], (count.get(nums[j]) || 0) + 1);
                if (count.get(nums[j]) > k) {
                    break;
                }
                res = Math.max(res, j - i + 1);
            }
        }
        return res;
    }
}

public class Solution {
    public int MaxSubarrayLength(int[] nums, int k) {
        int n = nums.Length, res = 0;

        for (int i = 0; i < n; i++) {
            Dictionary<int, int> count = new Dictionary<int, int>();
            for (int j = i; j < n; j++) {
                if (!count.ContainsKey(nums[j])) count[nums[j]] = 0;
                count[nums[j]]++;
                if (count[nums[j]] > k) {
                    break;
                }
                res = Math.Max(res, j - i + 1);
            }
        }
        return res;
    }
}

func maxSubarrayLength(nums []int, k int) int {
    n, res := len(nums), 0

    for i := 0; i < n; i++ {
        count := make(map[int]int)
        for j := i; j < n; j++ {
            count[nums[j]]++
            if count[nums[j]] > k {
                break
            }
            if j-i+1 > res {
                res = j - i + 1
            }
        }
    }
    return res
}

class Solution {
    fun maxSubarrayLength(nums: IntArray, k: Int): Int {
        val n = nums.size
        var res = 0

        for (i in 0 until n) {
            val count = HashMap<Int, Int>()
            for (j in i until n) {
                count[nums[j]] = count.getOrDefault(nums[j], 0) + 1
                if (count[nums[j]]!! > k) {
                    break
                }
                res = maxOf(res, j - i + 1)
            }
        }
        return res
    }
}

class Solution {
    func maxSubarrayLength(_ nums: [Int], _ k: Int) -> Int {
        let n = nums.count
        var res = 0

        for i in 0..<n {
            var count = [Int: Int]()
            for j in i..<n {
                count[nums[j], default: 0] += 1
                if count[nums[j]]! > k {
                    break
                }
                res = max(res, j - i + 1)
            }
        }
        return res
    }
}

impl Solution {
    pub fn max_subarray_length(nums: Vec<i32>, k: i32) -> i32 {
        let n = nums.len();
        let mut res = 0;

        for i in 0..n {
            let mut count = HashMap::new();
            for j in i..n {
                *count.entry(nums[j]).or_insert(0) += 1;
                if count[&nums[j]] > k {
                    break;
                }
                res = res.max((j - i + 1) as i32);
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Sliding Window

Intuition

Instead of restarting from scratch for each position, we can maintain a sliding window that always represents a valid subarray. When adding an element causes a frequency violation, we shrink the window from the left until the constraint is satisfied again. This way, we only process each element twice at most: once when entering and once when leaving the window.

Algorithm

Use two pointers l (left) and r (right) to define the current window.
Maintain a hash map to track the frequency of each element in the window.
For each right pointer position, add the current element to the frequency map.
While the newly added element's frequency exceeds k, shrink the window by incrementing l and decrementing the corresponding frequency.
Update res with the current window size r - l + 1.
Return the maximum length found.

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        res = 0
        count = defaultdict(int)
        l = 0
        for r in range(len(nums)):
            count[nums[r]] += 1
            while count[nums[r]] > k:
                count[nums[l]] -= 1
                l += 1
            res = max(res, r - l + 1)
        return res

public class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        int res = 0;
        Map<Integer, Integer> count = new HashMap<>();
        int l = 0;

        for (int r = 0; r < nums.length; r++) {
            count.put(nums[r], count.getOrDefault(nums[r], 0) + 1);
            while (count.get(nums[r]) > k) {
                count.put(nums[l], count.get(nums[l]) - 1);
                l++;
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        int res = 0;
        unordered_map<int, int> count;
        int l = 0;

        for (int r = 0; r < nums.size(); r++) {
            count[nums[r]]++;
            while (count[nums[r]] > k) {
                count[nums[l]]--;
                l++;
            }
            res = max(res, r - l + 1);
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    maxSubarrayLength(nums, k) {
        let res = 0;
        let count = new Map();
        let l = 0;

        for (let r = 0; r < nums.length; r++) {
            count.set(nums[r], (count.get(nums[r]) || 0) + 1);
            while (count.get(nums[r]) > k) {
                count.set(nums[l], count.get(nums[l]) - 1);
                l++;
            }
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

public class Solution {
    public int MaxSubarrayLength(int[] nums, int k) {
        int res = 0;
        Dictionary<int, int> count = new Dictionary<int, int>();
        int l = 0;

        for (int r = 0; r < nums.Length; r++) {
            if (!count.ContainsKey(nums[r])) count[nums[r]] = 0;
            count[nums[r]]++;
            while (count[nums[r]] > k) {
                count[nums[l]]--;
                l++;
            }
            res = Math.Max(res, r - l + 1);
        }
        return res;
    }
}

func maxSubarrayLength(nums []int, k int) int {
    res := 0
    count := make(map[int]int)
    l := 0

    for r := 0; r < len(nums); r++ {
        count[nums[r]]++
        for count[nums[r]] > k {
            count[nums[l]]--
            l++
        }
        if r-l+1 > res {
            res = r - l + 1
        }
    }
    return res
}

class Solution {
    fun maxSubarrayLength(nums: IntArray, k: Int): Int {
        var res = 0
        val count = HashMap<Int, Int>()
        var l = 0

        for (r in nums.indices) {
            count[nums[r]] = count.getOrDefault(nums[r], 0) + 1
            while (count[nums[r]]!! > k) {
                count[nums[l]] = count[nums[l]]!! - 1
                l++
            }
            res = maxOf(res, r - l + 1)
        }
        return res
    }
}

class Solution {
    func maxSubarrayLength(_ nums: [Int], _ k: Int) -> Int {
        var res = 0
        var count = [Int: Int]()
        var l = 0

        for r in 0..<nums.count {
            count[nums[r], default: 0] += 1
            while count[nums[r]]! > k {
                count[nums[l]]! -= 1
                l += 1
            }
            res = max(res, r - l + 1)
        }
        return res
    }
}

impl Solution {
    pub fn max_subarray_length(nums: Vec<i32>, k: i32) -> i32 {
        let mut res = 0;
        let mut count = HashMap::new();
        let mut l = 0;

        for r in 0..nums.len() {
            *count.entry(nums[r]).or_insert(0) += 1;
            while count[&nums[r]] > k {
                *count.get_mut(&nums[l]).unwrap() -= 1;
                l += 1;
            }
            res = res.max((r - l + 1) as i32);
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Sliding Window (Optimal)

Intuition

We can optimize further by observing that we only care about finding the maximum window size. Once we find a valid window of size w, we never need a smaller one. So instead of shrinking the window completely when invalid, we just slide it: move both left and right pointers by one. The window size either stays the same or grows, never shrinks. This guarantees we find the maximum valid window.

Algorithm

Track cnt, the count of elements whose frequency exceeds k.
For each right pointer, increment the element's frequency and update cnt if it just exceeded k.
If cnt > 0 (window is invalid), slide the window by moving the left pointer once. Before moving, check if the left element's frequency was above k and decrement cnt accordingly.
The window size never shrinks, so after processing all elements, the answer is len(nums) - l.

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        count = defaultdict(int)
        l = res = 0
        cnt = 0  # count of numbers with freq > k
        for r in range(len(nums)):
            count[nums[r]] += 1
            cnt += count[nums[r]] > k
            if cnt > 0:
                cnt -= count[nums[l]] > k
                count[nums[l]] -= 1
                l += 1
        return len(nums) - l

public class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        HashMap<Integer, Integer> count = new HashMap<>();
        int l = 0, cnt = 0; // count of numbers with freq > k
        for (int r = 0; r < nums.length; r++) {
            count.put(nums[r], count.getOrDefault(nums[r], 0) + 1);
            if (count.get(nums[r]) > k) cnt++;
            if (cnt > 0) {
                if (count.get(nums[l]) > k) cnt--;
                count.put(nums[l], count.get(nums[l]) - 1);
                l++;
            }
        }
        return nums.length - l;
    }
}

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        int l = 0, cnt = 0; // count of numbers with freq > k
        for (int r = 0; r < nums.size(); r++) {
            count[nums[r]]++;
            cnt += count[nums[r]] > k;
            if (cnt > 0) {
                cnt -= count[nums[l]] > k;
                count[nums[l]]--;
                l++;
            }
        }
        return nums.size() - l;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    maxSubarrayLength(nums, k) {
        let count = new Map();
        let l = 0,
            cnt = 0; // count of numbers with freq > k
        for (let r = 0; r < nums.length; r++) {
            count.set(nums[r], (count.get(nums[r]) || 0) + 1);
            if (count.get(nums[r]) > k) cnt++;
            if (cnt > 0) {
                if (count.get(nums[l]) > k) cnt--;
                count.set(nums[l], count.get(nums[l]) - 1);
                l++;
            }
        }
        return nums.length - l;
    }
}

public class Solution {
    public int MaxSubarrayLength(int[] nums, int k) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        int l = 0, cnt = 0; // count of numbers with freq > k
        for (int r = 0; r < nums.Length; r++) {
            if (!count.ContainsKey(nums[r])) count[nums[r]] = 0;
            count[nums[r]]++;
            if (count[nums[r]] > k) cnt++;
            if (cnt > 0) {
                if (count[nums[l]] > k) cnt--;
                count[nums[l]]--;
                l++;
            }
        }
        return nums.Length - l;
    }
}

func maxSubarrayLength(nums []int, k int) int {
    count := make(map[int]int)
    l, cnt := 0, 0 // count of numbers with freq > k
    for r := 0; r < len(nums); r++ {
        count[nums[r]]++
        if count[nums[r]] > k {
            cnt++
        }
        if cnt > 0 {
            if count[nums[l]] > k {
                cnt--
            }
            count[nums[l]]--
            l++
        }
    }
    return len(nums) - l
}

class Solution {
    fun maxSubarrayLength(nums: IntArray, k: Int): Int {
        val count = HashMap<Int, Int>()
        var l = 0
        var cnt = 0 // count of numbers with freq > k
        for (r in nums.indices) {
            count[nums[r]] = count.getOrDefault(nums[r], 0) + 1
            if (count[nums[r]]!! > k) cnt++
            if (cnt > 0) {
                if (count[nums[l]]!! > k) cnt--
                count[nums[l]] = count[nums[l]]!! - 1
                l++
            }
        }
        return nums.size - l
    }
}

class Solution {
    func maxSubarrayLength(_ nums: [Int], _ k: Int) -> Int {
        var count = [Int: Int]()
        var l = 0
        var cnt = 0 // count of numbers with freq > k
        for r in 0..<nums.count {
            count[nums[r], default: 0] += 1
            if count[nums[r]]! > k {
                cnt += 1
            }
            if cnt > 0 {
                if count[nums[l]]! > k {
                    cnt -= 1
                }
                count[nums[l]]! -= 1
                l += 1
            }
        }
        return nums.count - l
    }
}

impl Solution {
    pub fn max_subarray_length(nums: Vec<i32>, k: i32) -> i32 {
        let mut count = HashMap::new();
        let mut l = 0;
        let mut cnt = 0; // count of numbers with freq > k
        for r in 0..nums.len() {
            let freq = count.entry(nums[r]).or_insert(0);
            *freq += 1;
            if *freq > k {
                cnt += 1;
            }
            if cnt > 0 {
                let lf = count.get_mut(&nums[l]).unwrap();
                if *lf > k {
                    cnt -= 1;
                }
                *lf -= 1;
                l += 1;
            }
        }
        (nums.len() - l) as i32
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Forgetting to Decrement Frequency When Shrinking the Window

When the left pointer moves, you must decrement the frequency count of the element being removed from the window. Failing to do this causes the frequency map to retain stale counts, leading to incorrect constraint checks and wrong answers.

Using the Wrong Comparison Operator for the Constraint

The problem asks for elements appearing "at most k times," meaning frequency should be <= k. Using < k instead of <= k (or > k for violation checks) will incorrectly shrink the window too early or allow invalid windows.

Not Updating the Result at the Right Time

In sliding window problems, update the maximum length after ensuring the window is valid, not before. Updating before shrinking the window can record an invalid window size, resulting in an answer that exceeds the actual longest valid subarray.