Subarrays with K different ints

Count contiguous subarrays containing exactly K distinct integers.

sliding-window two-pointers hashmap counting

Given a list of integers `nums` and an integer `k`, return the number of contiguous subarrays that contain **exactly** `k` distinct values. Subarrays are non-empty contiguous sequences of elements. The function signature is `def subarrays_with_k_distinct(nums: list[int], k: int) -> int:`. Handle all cases including `k = 0` (there are no subarrays with zero distinct elements because subarrays are non-empty, so return 0).

Constraints

`0 <= len(nums) <= 10^5`
`0 <= k <= len(nums)`
Each element in `nums` is an integer in the range `-10^5` to `10^5`. Your solution should run in O(n) time and O(n) space (or better).

Example

>>> subarrays_with_k_distinct([1,2,1,2,3], 2)
7
>>> subarrays_with_k_distinct([1,2,1,3,4], 3)
3
>>> subarrays_with_k_distinct([1,1,1,1], 1)
10
>>> subarrays_with_k_distinct([1,2,3], 0)
0

40 points ~40 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use the classic trick: number of subarrays with at most K distinct elements minus number with at most K-1.

In the sliding window, maintain a frequency counter and a variable `distinct` counting keys with frequency > 0.

The formula: answer = at_most(k) - at_most(k-1). Implement a helper function for at most.

Be careful with k = 0 to avoid negative k in the at_most helper.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.