Workspace

Problem workspace

3 day streakD

Subarrays with Exactly K Distinct

HardSliding WindowCounting windows

The challenge

Count nonempty contiguous subarrays containing exactly k distinct values.

Integer array; k ≥ 0. Empty input or k = 0 returns 0.

Example

[1, 2, 1, 2, 3], k = 2 → 7.

Use the walkthrough below to inspect the input and each state change.

See Exactly K distinct, step by step

Expand, shrink, and inspect the window state.

5 elements · zero-based indicesk = 2
Sliding window over 5 elementsThe current window is empty. Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.Empty window · L = 0, R = -11021122334
Current windowRecorded answerOutside window
Left
0
Right
-1
Length
0
Step 01 / 32

Start with an empty window

Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.

left = 0; right = −1

Answer so far

0
View exact input

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

Current window is empty.

Put it into code

Exactly k is not preserved by removing a left element. Count at most k and at most k − 1 independently, then subtract.

Indices are zero-based. C++ uses C++17 or later.

def exactly_k_distinct(nums, k):
    def at_most(budget):
        if budget < 0:
            return 0
        count = {}
        left = total = 0
        for right, value in enumerate(nums):
            count[value] = count.get(value, 0) + 1
            while len(count) > budget:
                old = nums[left]
                count[old] -= 1
                if count[old] == 0:
                    del count[old]
                left += 1
            total += right - left + 1
        return total
    return at_most(k) - at_most(k - 1)

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap