Sliding Window — Subarrays with K Different Integers

↗ LeetCode: Subarrays with K Different Integers · Hard · pattern chapter →

Asked atGoogleAmazon

Given an integer array nums and integer k, return the number of contiguous subarrays containing exactly k distinct integers.

Example 1 — nums = [1,2,1,2,3], k = 2 → 7 (subarrays: [1,2], [2,1], [1,2], [2,1,2], [1,2,1], [1,2,1,2], [2,1,2,1]… actually 7 with exactly 2 distinct) Example 2 — nums = [1,2,1,3,4], k = 3 → 3Example 3 — nums = [1,1,1], k = 1 → 6 (each of [1], [1], [1], [1,1], [1,1], [1,1,1])

Constraints — 1 ≤ n ≤ 2 · 10⁴; 1 ≤ nums[i] ≤ n; 1 ≤ k ≤ n. Brute enumerates every subarray in O(n²) = 4·10⁸ ops at n=2·10⁴ (borderline TLE). Two sliding windows (≤k − ≤k−1) run in O(n) = 2·10⁴ ops.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Enumerate every subarray

Intuition. Count distinct in each [i, j]; if exactly k, increment.

int subarraysWithKDistinctBrute(int[] nums, int k) {
    int n = nums.length, count = 0;
    for (int i = 0; i < n; i++) {
        Set<Integer> d = new HashSet<>();
        for (int j = i; j < n; j++) {
            d.add(nums[j]);
            if (d.size() == k) count++;
            else if (d.size() > k) break;
        }
    }
    return count;
}

Complexity — Time O(n²); Space O(n).

---

Approach 2 — Two windows: atMost(k) − atMost(k−1)

Insight from brute. "Exactly k" is hard to slide directly. But exactly(k) = atMost(k) - atMost(k-1). Each atMost is a standard sliding window with a distinct counter.

Why it works. Every subarray with ≤ k distinct is counted by atMost(k). Subtract those with ≤ k−1 distinct — what remains is exactly k distinct.

int subarraysWithKDistinct(int[] nums, int k) {
    return atMost(nums, k) - atMost(nums, k - 1);
}
int atMost(int[] nums, int k) {
    if (k < 0) return 0;
    Map<Integer, Integer> cnt = new HashMap<>();
    int left = 0, res = 0;
    for (int right = 0; right < nums.length; right++) {
        cnt.merge(nums[right], 1, Integer::sum);
        while (cnt.size() > k) {
            cnt.merge(nums[left], -1, Integer::sum);
            if (cnt.get(nums[left]) == 0) cnt.remove(nums[left]);
            left++;
        }
        res += right - left + 1; // # of subarrays ending at `right`
    }
    return res;
}

Execution Trace

atMost(k=2) — nums=[1,2,1,2,3]

Step 1 / 51 subarray ending at 0

Then atMost(2) - atMost(1) = 12 - 5 = 7.

Complexity — Time O(n) — two O(n) sweeps; Space O(k).

---

Try it yourself

Complexity summary

Approach	Time	Space	Interview grade
Every subarray	O(n²)	O(n)	baseline
Two atMost windows	O(n)	O(k)	expected optimum

When to use which

• "Exactly k" phrasing → immediately go to atMost(k) - atMost(k-1).
• "At most k" → single sliding window.
• "At least k" → count total n·(n+1)/2 minus atMost(k-1).
• "Return the subarrays themselves" → change the counting to enumeration; loses O(n).

✨AI Study CompanionBeta

Related problems

• Binary Subarrays With Sum — same at-most trick with sums
• Count Number of Nice Subarrays — same trick, k odd numbers
• Longest Substring with At Most K Distinct Characters — length variant
• Subarray Product Less Than K

Was this page helpful?

📚 Related problems

• → Number Of Substrings Containing All Three Characters
• → Minimum Window Substring
• → Count Number Of Nice Subarrays