Problem 7.7 · Sliding WindowHard

Subarrays with K Different Integers

What it teaches: Count "exactly K" as atMost(K) − atMost(K − 1), where each at-most count is a simple window.

Practise it on judges as “Subarrays with K Different Integers”.

The problem

Given nums and k, return the number of contiguous subarrays with exactly k distinct values.

Example 1

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

[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Example 2

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

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i], k ≤ n

Pattern clues in the wording

→ Count subarrays with "exactly K" of something
→ "At most K" would be a clean window

These clues point to Sliding Window: Variable Size: Grow the window with the right pointer; when it breaks a rule, shrink it from the left until it's valid again.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [1,2,1,2,3] k = 2	7
2	nums = [1,2,1,3,4] k = 3	3

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: two at-most windows · O(n)

Optimal: two at-most windows

Time O(n) Space O(n)

atMost(k): grow right, shrink while the distinct count exceeds k, and add right − left + 1 (every subarray ending at right that starts in the window). Answer = atMost(k) − atMost(k − 1).

Approach 1

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    private int atMost(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        int left = 0, total = 0;
        for (int right = 0; right < nums.length; right++) {
            count.merge(nums[right], 1, Integer::sum);
            while (count.size() > k) {
                int out = nums[left++];
                if (count.merge(out, -1, Integer::sum) == 0) count.remove(out);
            }
            total += right - left + 1;
        }
        return total;
    }
}

Verdict: Two linear passes.

Before you submit

Edge cases and common mistakes

Test these inputs

k = 1
k larger than the number of distinct values → 0
All equal values

Mistakes people make

Forgetting to remove keys at count 0, so count.size() is wrong.
atMost(0) must return 0 (the loop handles it: every window shrinks to empty).

Interview

Follow-up questions

Why does right − left + 1 count all valid subarrays ending at right?

Command Palette

The problem

Approaches

Optimal: two at-most windows

Edge cases and common mistakes

Follow-up questions

Related problems