Subarrays with K Different Integers — LC 992 Hard Sliding Window Decomposition

Problem Statement#

Given an integer array nums and integer k, count subarrays containing exactly k distinct integers.

Constraints:

• 1 less than or equal to nums.length less than or equal to 2 times 10 to the 4
• 1 less than or equal to nums[i] less than or equal to nums.length
• 1 less than or equal to k less than or equal to nums.length

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

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

Why This Problem Matters#

LeetCode 992 — Subarrays with K Different Integers is the canonical "hard" sliding window problem at Google, Amazon, and Meta. It is the parent problem from which LC 1248 (Count Number of Nice Subarrays), LC 930 (Binary Subarrays with Sum), and LC 1358 (Number of Substrings Containing All Three Characters) all descend. If you can solve LC 992 cleanly, you can solve all of them.

The challenge: a window with exactly k distinct integers is not monotonic — adding an element can either keep distinct count the same or increment it, and removing can only decrement or keep. Trying to maintain "exactly k" with a single window collapses immediately.

The fix is the same decomposition that makes LC 1248 and LC 930 trivial: exactly(k) equals atMost(k) minus atMost(k - 1). Two atMost windows, each O(n), gives O(n) total.

The Core Insight#

atMost(k) counts subarrays with at most k distinct integers. This is monotonic: as right advances, distinct count can only grow; advance left while distinct count is greater than k, dropping each element from a frequency map.

For each valid window, every subarray ending at right with start in [left, right] is valid, contributing right - left + 1 to the count.

Then exactly(k) equals atMost(k) minus atMost(k - 1). Both calls are O(n) over the same input. Total complexity is O(n) time, O(n) space for the frequency map.

The proof is set difference: subarrays with at most k minus subarrays with at most k - 1 leaves exactly subarrays with exactly k.

Visual Dry Run#

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

atMost(2) is 12, atMost(1) is 5, answer 12 minus 5 equals 7.

Solution (Optimal)#

class Solution:
    def subarraysWithKDistinct(self, nums, k):
        def at_most(limit):
            if limit < 0:
                return 0
            freq = {}
            left, distinct, total = 0, 0, 0
            for right, value in enumerate(nums):
                if freq.get(value, 0) == 0:
                    distinct += 1
                freq[value] = freq.get(value, 0) + 1
                while distinct > limit:
                    freq[nums[left]] -= 1
                    if freq[nums[left]] == 0:
                        distinct -= 1
                    left += 1
                total += right - left + 1
            return total
        return at_most(k) - at_most(k - 1)

var subarraysWithKDistinct = function(nums, k) {
    const atMost = (limit) => {
        if (limit < 0) return 0;
        const freq = new Map();
        let left = 0, distinct = 0, total = 0;
        for (let right = 0; right < nums.length; right++) {
            const v = nums[right];
            if ((freq.get(v) || 0) === 0) distinct++;
            freq.set(v, (freq.get(v) || 0) + 1);
            while (distinct > limit) {
                const lv = nums[left];
                freq.set(lv, freq.get(lv) - 1);
                if (freq.get(lv) === 0) distinct--;
                left++;
            }
            total += right - left + 1;
        }
        return total;
    };
    return atMost(k) - atMost(k - 1);
};

Time: O(n) — two linear sliding windows. Space: O(n) for the frequency map.

Common Mistakes#

• Trying to maintain a single window with exactly k distinct values. The window is not monotonic.
• Not decrementing distinct when a frequency drops to zero. Stale counts cause permanent bloat.
• Forgetting to guard atMost(-1) for k = 0. The helper would loop forever.
• Counting windows as 1 instead of right - left + 1.
• Using Python dict default to 0 but not deleting entries — fine logically but wastes memory in long streams.

Interview Tips#

• Open with the trick: "Exactly k equals atMost(k) minus atMost(k - 1)."
• Walk through one full atMost call before composing the answer.
• Mention that this is the parent of LC 1248 and LC 930.
• Note the O(n) space cost from the frequency map.
• If asked, sketch the proof by set difference.

Follow-up Questions#

• What if nums contains negative values? The algorithm is unaffected; it depends only on equality.
• Find the longest subarray with exactly k distinct integers. Track length during atMost(k) and exclude when atMost(k - 1) would also accept.
• What if the alphabet is large but values are characters? Use a fixed-size 256 array instead of a map.
• Stream variant: process online. Maintain the same window state and update as items arrive.
• Count subarrays with at least k distinct integers. atMost(n) minus atMost(k - 1).

Key Takeaways#

• LeetCode 992 — Subarrays with K Different Integers solves in O(n) time, O(n) space.
• exactly(k) equals atMost(k) minus atMost(k - 1) is the universal exact-count trick.
• The single-window approach fails because distinct-count is not monotonic in both directions.
• Decrement distinct only when a frequency hits zero in the map.
• Asked at Google, Amazon, Meta, and Microsoft as a hard sliding window screen.
• This problem is the parent of LC 1248, LC 930, and LC 1358.
• Counting trick right - left + 1 is shared with every atMost-style helper.