LeetCode #992 Hard

Subarrays with K Different Integers

Return the number of subarrays containing exactly k distinct integers.

sliding-windowhashmaparray

02

Intuition

💡

Marked Hard, but the trap is identical to Count Nice Subarrays: trying to slide one window on "exactly k distinct" directly. Exactly-k is not monotone, so there is no shrink rule that keeps the window valid — sometimes adding an element should grow it, sometimes it should have shrunk first, and no single pointer rule covers both. At-most-k is monotone, so compute atMost(k) - atMost(k-1) again, this time over a frequency map instead of a parity count, and don't forget to delete zeroed keys or the map lies about the distinct count.

03

Approach

1

See why a single window fails

A window enforcing exactly k distinct has no valid shrink rule: removing an element might drop the distinct count below k, and adding one might push it above. There is no direction that reliably restores legality, which is exactly the property a sliding window requires.

2

Write atMost(k) over a frequency map

Grow right and increment freq[nums[right]]. While len(freq) > k, decrement the left element's count, delete the key when it reaches zero, and advance left. Add right - left + 1 after each step — that is how many subarrays ending here have at most k distinct values.

3

Subtract

atMost(k) - atMost(k-1) gives exactly k. Each pass is O(n) with O(k) space for the map, so the total is O(n) — comfortably better than the O(n^2) brute force, and the code is barely longer than the at-most version alone.

04

Solution & live demo

python

▶1class Solution:
▶2    def subarraysWithKDistinct(self, nums, k):
▶3        def atMost(m):
▶4            freq = {}
▶5            left = total = 0
▶6            for right, v in enumerate(nums):
▶7                freq[v] = freq.get(v, 0) + 1
▶8                while len(freq) > m:
▶9                    out = nums[left]
▶10                    freq[out] -= 1
▶11                    if freq[out] == 0:
▶12                        del freq[out]
▶13                    left += 1
▶14                total += right - left + 1
▶15            return total
▶16        return atMost(k) - atMost(k - 1)

05

Edge cases

k = 1

atMost(0) is 0, so the answer is simply the count of constant runs.

k > number of distinct values

Both terms coincide and the difference is 0.

Forgetting to delete zeroed keys

len(freq) overstates the distinct count and the window over-shrinks — the same trap as the k-distinct substring problem.

All elements identical

Only k = 1 gives a non-zero answer, namely n(n+1)/2.

06

Complexity

Time

O(n)

Space

O(k)

Two linear passes; the map holds at most k+1 keys.