Subarrays with K Different Integers [Hard] — The Sliding Window Subtraction Trick

Problem Statement#

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good subarray is a subarray where the number of different integers in that subarray is exactly k.

Example 1:

Input:  nums = [1, 2, 1, 2, 3],  k = 2
Output: 7
Explanation: Subarrays with exactly 2 distinct integers:
  [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
Explanation: [1,2,1,3], [2,1,3], [1,3,4]

Constraints:

• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i] <= nums.length
• 1 <= k <= nums.length

Why This Problem Matters#

LeetCode 992 is rated Hard, and it earns that rating — not because the code is long, but because the key insight is genuinely non-obvious. Almost every candidate who sees this problem for the first time tries to maintain a sliding window with exactly k distinct elements. That approach breaks down almost immediately: when the window has exactly k distinct elements, you can't shrink from the left because you do not know whether the element you remove appears again later inside the window.

The real trick is a reduction: transform the "exactly k" question into two "at most k" questions, then subtract. Once you see that reduction, the implementation is straightforward — a standard shrinkable sliding window that anyone who has solved LC 3 (Longest Substring Without Repeating Characters) will recognize instantly.

Why does FAANG care about this problem? Because it tests three things simultaneously:

1. Pattern recognition: Can you see that "exactly" is harder than "at most" and make the reduction?
2. Sliding window mastery: Can you implement the shrinkable window correctly, including the edge case where a removed element drops to zero count in the map?
3. Generalisation: The same reduction (exactly K = atMost(K) - atMost(K-1)) applies to a whole family of problems — LC 340, LC 904, LC 930, and others. Knowing this pattern is worth far more than solving this one problem.

Google has asked this problem directly in phone screens. Amazon uses it in online assessments. If you are preparing for a senior engineering role, you should be able to write the solution cleanly from memory and explain every line.

The "Exactly K = at most K minus at most K-1" Insight#

Let's build up to the insight from first principles.

Why "exactly K" is hard to maintain directly#

Imagine you have a sliding window [left, right]. You want to keep exactly k distinct elements inside. As you advance right, the window eventually picks up its k-th distinct element — great. But what happens when you pick up a (k+1)-th distinct element? You need to shrink from the left. However, shrinking removes one occurrence of nums[left]. If that element still appears elsewhere in the window, the distinct count does not drop — you wasted a shrink. If it does not appear again, the count drops. You cannot know which case applies without counting frequencies, and even then the logic becomes fragile.

The shrinkable window works beautifully for "at most k" but not for "exactly k" directly.

The reduction#

Here is the key observation:

exactly(k) = atMost(k) - atMost(k - 1)

Think of it set-theoretically. atMost(k) counts every subarray whose distinct count is 1, 2, 3, ..., or k. atMost(k-1) counts every subarray whose distinct count is 1, 2, ..., or k-1. The difference is precisely those subarrays with distinct count equal to exactly k.

This is the same logic as "numbers from 1 to 10 that equal 7" = (count from 1 to 7) - (count from 1 to 6).

Why atMost(k) is easy#

For "at most k distinct elements," the shrinkable window works perfectly:

• Expand right: add nums[right] to the frequency map.
• If the map has more than k keys, shrink left until it has at most k keys again.
• At every position of right, every subarray ending at right and starting anywhere from left to right is valid. That count is right - left + 1.
• Sum those counts across all positions of right.

This runs in O(n) time because left only ever moves forward.

Visual Dry Run#

Let's trace nums = [1, 2, 1, 2, 3], k = 2 through both atMost(2) and atMost(1).

atMost(2) — subarrays with at most 2 distinct integers#

We maintain a frequency map and count valid subarrays ending at each right.

right=0  val=1  map={1:1}  distinct=1  left=0  subarrays ending here: [1]          count += 1  total=1
right=1  val=2  map={1:1,2:1}  distinct=2  left=0  subarrays: [2],[1,2]             count += 2  total=3
right=2  val=1  map={1:2,2:1}  distinct=2  left=0  subarrays: [1],[2,1],[1,2,1]    count += 3  total=6
right=3  val=2  map={1:2,2:2}  distinct=2  left=0  subarrays: [2],[1,2],[2,1,2],[1,2,1,2]  count += 4  total=10
right=4  val=3  map={1:2,2:2,3:1}  distinct=3 > 2  => shrink:
    remove nums[0]=1  map={1:1,2:2,3:1}  distinct=3  left=1
    remove nums[1]=2  map={1:1,2:1,3:1}  distinct=3  left=2
    remove nums[2]=1  map={1:0->del,2:1,3:1}={2:1,3:1}  distinct=2  left=3
  subarrays ending at right=4 from left=3: [3],[2,3]  count += 2  total=12

atMost(2) = 12

atMost(1) — subarrays with at most 1 distinct integer#

right=0  val=1  map={1:1}  distinct=1  left=0  count += 1  total=1
right=1  val=2  map={1:1,2:1}  distinct=2 > 1  => shrink:
    remove nums[0]=1  map={2:1}  distinct=1  left=1
  count += 1  total=2
right=2  val=1  map={2:1,1:1}  distinct=2 > 1  => shrink:
    remove nums[1]=2  map={1:1}  distinct=1  left=2
  count += 1  total=3
right=3  val=2  map={1:1,2:1}  distinct=2 > 1  => shrink:
    remove nums[2]=1  map={2:1}  distinct=1  left=3
  count += 1  total=4
right=4  val=3  map={2:1,3:1}  distinct=2 > 1  => shrink:
    remove nums[3]=2  map={3:1}  distinct=1  left=4
  count += 1  total=5

atMost(1) = 5

Final answer#

exactly(2) = atMost(2) - atMost(1) = 12 - 5 = 7

Which matches the expected output. The seven subarrays are: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Common Mistakes#

Mistake 1: Trying to maintain exactly k distinct directly#

The most common wrong approach: shrink the window from the left whenever distinct count exceeds k, and add right - left + 1 to the answer whenever distinct count equals exactly k. This misses subarrays. Consider [1,1,2] with k=1: when right=1 and left=0, distinct=1, you add 2. When right=2, distinct becomes 2, you shrink, distinct becomes 1 again with left=1, and you add 1. Total = 3. But the correct answer for atMost(1) on [1,1,2] is 4 ([1], [1], [1,1], [2]), and for exactly(1) it's 3 — coincidentally right here but wrong on many other inputs. The logic collapses for longer duplicated sequences.

Mistake 2: Forgetting to delete the key when frequency hits zero#

When shrinking the window, you decrement freq[nums[left]]. If that value becomes 0, you must delete the key from the map. If you leave zero-frequency keys in the map, len(freq) stays inflated and your shrink condition len(freq) > k fires at the wrong time. This is an extremely common off-by-one class of bug in sliding window problems.

# WRONG — leaves ghost keys
freq[nums[left]] -= 1
left += 1
 
# CORRECT — removes key when count hits zero
freq[nums[left]] -= 1
if freq[nums[left]] == 0:
    del freq[nums[left]]
left += 1

Mistake 3: Off-by-one in the k-1 call#

The reduction is atMost(k) - atMost(k - 1). A common typo is writing atMost(k) - atMost(k) (subtracting with the same argument) or atMost(k - 1) - atMost(k - 2). Make sure the subtracted call uses exactly k - 1.

Mistake 4: Miscounting valid subarrays in the inner loop#

After every adjustment of left, the number of new valid subarrays that end at the current right is right - left + 1 — not right - left. This represents subarrays starting at left, left+1, ..., right, all of which end at right. Forgetting the +1 systematically undercounts by one subarray per step.

Mistake 5: Not handling k=0#

The constraints guarantee k >= 1, but if you ever adapt this helper to a variant where k could be 0, atMost(0) should return 0 (no subarray can have a negative or zero distinct count usefully). Add an early return guard in the helper when repurposing this code.

Solutions#

Python#

from collections import defaultdict
 
def subarraysWithKDistinct(nums: list[int], k: int) -> int:
    # Use the reduction: exactly(k) = atMost(k) - atMost(k-1)
    def at_most(limit: int) -> int:
        # freq tracks how many times each number appears in the current window
        freq = defaultdict(int)
        left = 0          # left boundary of the sliding window
        result = 0        # accumulates total valid subarray count
 
        for right in range(len(nums)):
            # Expand the window to include nums[right]
            freq[nums[right]] += 1
 
            # If the window now has more than `limit` distinct elements,
            # shrink from the left until we are back to at most `limit`
            while len(freq) > limit:
                freq[nums[left]] -= 1
                # Remove the key entirely when its count reaches zero;
                # otherwise len(freq) stays inflated with ghost entries
                if freq[nums[left]] == 0:
                    del freq[nums[left]]
                left += 1  # slide the left boundary one step right
 
            # Every subarray ending at `right` and starting anywhere
            # from `left` to `right` has at most `limit` distinct integers.
            # There are exactly (right - left + 1) such subarrays.
            result += right - left + 1
 
        return result
 
    # Subarrays with exactly k distinct = (at most k) - (at most k-1)
    return at_most(k) - at_most(k - 1)

JavaScript#

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function subarraysWithKDistinct(nums, k) {
  // Use the reduction: exactly(k) = atMost(k) - atMost(k-1)
  return atMost(nums, k) - atMost(nums, k - 1);
}
 
function atMost(nums, limit) {
  // freq maps each number to its occurrence count in the current window
  const freq = new Map();
  let left = 0;    // left boundary of the sliding window
  let result = 0;  // total count of valid subarrays
 
  for (let right = 0; right < nums.length; right++) {
    const rightVal = nums[right];
 
    // Expand: include nums[right] in the window
    freq.set(rightVal, (freq.get(rightVal) ?? 0) + 1);
 
    // Shrink from the left until we have at most `limit` distinct elements
    while (freq.size > limit) {
      const leftVal = nums[left];
      freq.set(leftVal, freq.get(leftVal) - 1);
      // Delete the key when count reaches zero to keep freq.size accurate
      if (freq.get(leftVal) === 0) {
        freq.delete(leftVal);
      }
      left++; // advance the left boundary
    }
 
    // All subarrays ending at `right` with start in [left..right] are valid.
    // Count = right - left + 1
    result += right - left + 1;
  }
 
  return result;
}

Complexity Analysis#

The sliding window approach calls atMost twice, and each call runs in O(n) because left is monotonically non-decreasing — it only ever moves right. The total number of left-moves across the entire loop is at most n. So each atMost call is O(n), and the overall solution is O(n).

Space is O(k) for the frequency map, since the window shrinks whenever the map exceeds k keys, keeping its size bounded by k + 1 at any moment (it hits k+1 briefly, then we shrink).

Follow-up Questions#

Strong candidates are expected to connect this problem to adjacent problems. Here are the three most important follow-ups an interviewer might raise.

LC 340 — Longest Substring with At Most K Distinct Characters#

Prompt: Given a string s and integer k, return the length of the longest substring that contains at most k distinct characters.

This is a direct application of the atMost(k) helper from our solution, but instead of counting valid subarrays you track the maximum window length. The shrinkable window is identical — just replace result += right - left + 1 with result = max(result, right - left + 1).

atMost helper → track max window size instead of summing counts

LC 904 — Fruit Into Baskets#

Prompt: You have an array of fruits (integers). You have two baskets and can only pick one type of fruit per basket. Find the longest subarray you can pick from a contiguous section.

This is exactly atMost(k=2) on the fruit array — find the longest window with at most 2 distinct values. Once you recognise the disguise, the solution is a single call to the atMost helper with limit=2 and tracking max window size.

"Two baskets" = k=2 → longest subarray with at most 2 distinct elements

LC 930 — Binary Subarrays With Sum#

Prompt: Given a binary array nums and an integer goal, return the number of subarrays with sum equal to goal.

This uses the same reduction pattern but for sums instead of distinct counts:

exactly(goal) = atMost(goal) - atMost(goal - 1)

where atMost(goal) counts subarrays whose sum is at most goal. The sliding window logic is analogous: expand right, shrink left when sum exceeds the limit. This demonstrates that the reduction is a general technique, not something unique to "distinct counts."

This Pattern Solves#

Once you internalise the exactly(k) = atMost(k) - atMost(k-1) pattern, a whole class of problems opens up:

The pattern shows up anywhere you need to count subarrays satisfying an exact condition that is hard to maintain directly but easy to measure as a "at most" prefix difference.

Key Takeaways#

• The key formula: exactly(k) = atMost(k) - atMost(k-1). This transforms an "exactly k distinct" constraint into two "at most" sliding window problems.
• The atMost(k) helper uses a shrinkable window: expand right always, shrink left when len(freq) > k. At each step, add right - left + 1 new valid subarrays.
• When a frequency drops to 0 in the map, delete the key — otherwise len(freq) stays inflated and the shrink condition never triggers correctly.
• O(n) time, O(k) space for the frequency map; two calls to atMost = O(n) total.
• The same trick applies to LC 930 (Binary Subarrays With Sum: sum == goal), LC 1248 (Count Nice Subarrays: odds == k), and similar "exactly k" constraints.
• The number of valid subarrays added at each right step equals the window size right - left + 1 — this accounts for all subarrays ending at right with at most k distinct elements.
• Trigger pattern: whenever a problem says "subarray with exactly k [property]" and the property is monotone over subarray extension, apply atMost(k) - atMost(k-1).