How do you approach Subarrays with K Different Integers?

"Exactly k" is hard to maintain directly because shrinking the window can skip over it. Is there an easier quantity to count?

What is the time complexity of Subarrays with K Different Integers?

Time complexity: O(n) - two linear sliding-window passes. Space complexity: O(k) - the frequency map.

What are common mistakes on Subarrays with K Different Integers?

Shrinking with if instead of while - one removal is often not enough to restore the invariant. Recomputing the window's contents each step, which puts back the O(n²) the pattern exists to remove. Never recording the answer for a window that ends at the last index.

gitGood.dev

← Back to problems

Subarrays with K Different Integers

HardAlgorithms

Description

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

A good subarray is a contiguous, non-empty subarray of nums with exactly k different (distinct) integers.

For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.

Example 1

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

Output: 7

Explanation: Subarrays with exactly 2 different 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: Subarrays with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Example 3

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

Output: 6

Explanation: Every one of the 6 non-empty subarrays contains exactly 1 distinct integer.

Constraints

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

Subarrays with K Different Integers: approach, complexity and pitfalls

A hard sliding window problem, graded against 7 test cases (4 of them hidden).

The pattern: Sliding Window

A moving window over a contiguous run, expanding and contracting to hold an invariant.

Reach for it when you see: "Longest/shortest contiguous subarray or substring satisfying X."

If you are stuck

Show the 3-step hint ladder

"Exactly k" is hard to maintain directly because shrinking the window can skip over it. Is there an easier quantity to count?
Counting subarrays with AT MOST k distinct integers is a standard sliding window: for each right endpoint, every window start between left and right is valid.
exactly(k) = atMost(k) - atMost(k - 1). Run the at-most window twice.

The optimal approach

Show the approach: exactly(k) = atMost(k) - atMost(k-1)

Counting windows with *exactly* k distinct values does not fit a single sliding window, because validity is not monotonic as the window grows. But *at most k* is monotonic: maintain a window with at most k distinct values, and for each right endpoint, every subarray ending at `right` and starting at or after `left` qualifies - that's `right - left + 1` subarrays.

Subtracting `atMost(k-1)` from `atMost(k)` removes the subarrays with fewer than k distinct values, leaving exactly k.

Time: O(n) - two linear sliding-window passes
Space: O(k) - the frequency map

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Sliding Window mistakes

These apply to the pattern as a whole, not just this problem.

Shrinking with `if` instead of `while` - one removal is often not enough to restore the invariant.
Recomputing the window's contents each step, which puts back the O(n²) the pattern exists to remove.
Never recording the answer for a window that ends at the last index.