← DSA Atlas
Dedicated problem page · #992

Subarrays with K Different Integers

HardSliding WindowExactly-K via at-most-K minus at-most-(K-1)Sliding window with hash-map frequency counting
Solve on LeetCode ↗
992
HardSliding WindowSliding window with hash-map frequency countingExactly-K via at-most-K minus at-most-(K-1)

Subarrays with K Different Integers

Given an integer array nums and an integer k, a subarray is 'good' if it contains exactly k distinct integers. Return the number of good (contiguous) subarrays of nums.

Open official problem prompt ↗
In plain English

Count how many contiguous slices of the array hold precisely k different values — not fewer, not more.

Picture it like this

Imagine counting playlists that use exactly 2 genres. It is hard to filter for 'exactly 2' directly, but easy to count 'at most 2 genres' and 'at most 1 genre'. Subtract the second from the first and you are left with playlists using exactly 2.

Example
Input
nums = [1, 2, 1, 2, 3], k = 2
Output
7
Why
The subarrays with exactly 2 distinct values are [1,2], [2,1], [1,2], [2,1], [1,2,1], [2,1,2], and [1,2,1,2] — seven of them.
Constraints
1 <= nums.length <= 2 * 10^41 <= nums[i], k <= nums.length
Pattern lesson

See the pattern, then code

Exactly-K via at-most-K minus at-most-(K-1)
Recognition clue

You must count subarrays whose distinct-element count is EXACTLY a target. A window can't directly grow/shrink on an exact-equality condition, but 'at most k' is monotonic and slideable, so express exactly-k = atMost(k) - atMost(k-1).

↗
Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. For a fixed right end, the number of windows with at most m distinct values equals right - left + 1, where left is the smallest start keeping the window valid. Summing that over all right counts every at-most-m subarray in O(n). Subtracting the at-most-(k-1) total leaves only those with exactly k.

New words, made simpleKnow these before the algorithm
Distinct count
The number of different integer values currently inside the window (the number of keys in the frequency map).
At most k
A monotonic condition: if a window is valid, every sub-window inside it is also valid, which is what makes it slideable.
Window contribution
For each right endpoint, right - left + 1 new subarrays end at right and satisfy the constraint.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute force over all subarrays

n up to 2*10^4 makes n^2 borderline-to-slow and it does redundant recomputation.

For every start, expand to every end and count distinct values with a set.

Time O(n^2)Space O(n)
Best choiceatMost(k) - atMost(k-1)

Two linear passes; converts an un-slideable equality into two slideable inequalities.

Count subarrays with at most k distinct and subtract those with at most k-1, leaving exactly k.

Time O(n)Space O(k)
The rule we keep true

Invariant

In atMost(m), the window [left, right] always holds at most m distinct integers, and left is the smallest index for which that holds given the current right.

Why this is correct

Reasoning

Every subarray with at most k distinct values is counted by atMost(k); every subarray with at most k-1 distinct is counted by atMost(k-1). A subarray has exactly k distinct iff it is in the first set but not the second, so the difference is precisely the exactly-k count. Because 'at most m' is monotonic in left, each pointer moves forward only, giving linear time.

The algorithm in three movesSay these aloud before coding
1Write a helper atMost(m) that counts subarrays with at most m distinct integers using a sliding window

atMost(2): total = 12

2In the helper, extend right, add nums[right] to a frequency map, and shrink left while the map has more than m keys

atMost(1): total = 5

3Add right - left + 1 to the running total each step

answer = 12 - 5 = 7

4Return atMost(k) - atMost(k - 1)

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
12
23
34
1 · Readread 1 (idx0)
2 · Askdistinct <= 2?
3 · Update statecount={1:1}, left=0
4 · Resultres += 1 -> res=1
Key takeaway

The window [1,2,1,2] (indices 0-3) is the largest run holding exactly 2 distinct values before 3 forces a shrink.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 2-3Reduce exact-k to two at-most calls

    The public method simply returns at_most(k) - at_most(k - 1); all real work lives in the helper.

  2. 2
    Lines 4-7Helper setup

    A frequency dict tracks how many of each value are in the window; left and res are the window start and running count.

  3. 3
    Lines 8-10Extend right

    Add nums[right] to the map, increasing the distinct count only when a brand-new key appears.

  4. 4
    Lines 11-15Shrink while too many distinct

    While the map holds more than m keys, decrement the leftmost value and delete the key when its count hits zero, advancing left.

  5. 5
    Lines 16Count contributions

    Every window ending at right with start in [left, right] is valid, so add right - left + 1.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • k equal to the number of distinct values in the whole array (only the full array or large windows qualify)
  • All elements identical with k=1 (answer is n*(n+1)/2)
  • k larger than achievable distinct count is impossible given constraints since k <= nums.length, but atMost(k-1) with k=1 must return 0 cleanly
!

Common beginner mistakes

  • Trying to slide directly on 'exactly k' — the shrink condition is not monotonic, so it fails
  • Forgetting to delete a key when its frequency drops to 0, which corrupts len(count)
  • Off-by-one in the contribution: it is right - left + 1, not right - left
Check your understanding

Why can we count 'at most m' subarrays with a sliding window but not 'exactly m' directly?

More in Sliding Window

#3Longest Substring Without Repeating CharactersVariable-size sliding window with last-seen index#424Longest Repeating Character ReplacementVariable-size window constrained by replaceable slots#76Minimum Window SubstringShrinkable window covering a multiset requirement#30Substring with Concatenation of All WordsWord-aligned sliding window over fixed-length tokens#121Best Time to Buy and Sell StockRunning minimum with best forward difference#209Minimum Size Subarray SumShrinking window on a sum threshold