Generated by Codex with GPT 5.6 Sol High

Quick facts

Problem gist

Given an integer array nums and an integer k, count the nonempty contiguous subarrays that contain exactly k distinct values.

The word exactly makes the counting awkward. A normal sliding window is good at enforcing a one-sided condition such as “no more than k distinct values”: once a window has too many, move its left edge until it is valid again. But a valid window with exactly k distinct values may have several valid starting positions, so adding one answer for each right edge would miss subarrays.

The clean solution changes the question into one that a sliding window can count naturally, then recovers “exactly” with subtraction.

Deriving the optimal solution

Define at_most(limit) as the number of subarrays containing at most limit distinct values. Every subarray counted by at_most(k) falls into one of two disjoint groups: it contains at most k - 1 distinct values, or it contains exactly k. Therefore,

exactly(k) = at_most(k) - at_most(k - 1)

To compute at_most(limit), expand the right edge one element at a time and keep a frequency map for the current window. When a new value first enters the map, the distinct count increases. If that count exceeds limit, advance the left edge, decreasing frequencies and removing a value from the map when its frequency reaches zero.

After shrinking, [left, right] is the longest valid window ending at right. Every suffix of that window also has at most limit distinct values, so exactly right - left + 1 valid subarrays end at right. Adding that quantity for every right edge counts each valid subarray once.

Each array position enters a window once and leaves it at most once in each helper call. The two calls therefore take O(n) time overall. The frequency map uses O(d) extra space, where d is the number of distinct values in the active window and is at most min(n, k) for the at_most(k) call.

A small example

For nums = [1, 2, 1, 2, 3] and k = 2, at_most(2) counts 12 subarrays while at_most(1) counts 5. Their difference is 7, which is the number of subarrays with exactly two distinct values.

The important part is not memorizing those totals. It is seeing why the subtraction isolates the desired category: every subarray with zero or one distinct value appears in both counts and cancels, while every subarray with exactly two appears only in the first.

Python solution

The public method isolates the exact count. The helper owns the sliding-window invariant and handles a negative limit explicitly, which also makes the method well-defined for k = 0.

from collections import defaultdict
from collections.abc import Sequence


class Solution:
    """Count contiguous subarrays by their number of distinct values."""

    def subarraysWithKDistinct(self, nums: list[int], k: int) -> int:
        """Return the number of nonempty subarrays with exactly k distinct values."""
        if k <= 0:
            return 0

        return self._count_at_most(nums, k) - self._count_at_most(nums, k - 1)

    @staticmethod
    def _count_at_most(nums: Sequence[int], limit: int) -> int:
        """Count nonempty subarrays containing at most limit distinct values."""
        if limit < 0:
            return 0

        frequencies: dict[int, int] = defaultdict(int)
        left = 0
        distinct_count = 0
        subarray_count = 0

        for right, value in enumerate(nums):
            if frequencies[value] == 0:
                distinct_count += 1
            frequencies[value] += 1

            # Restore the invariant that the window has at most `limit`
            # distinct values.
            while distinct_count > limit:
                outgoing_value = nums[left]
                frequencies[outgoing_value] -= 1
                if frequencies[outgoing_value] == 0:
                    del frequencies[outgoing_value]
                    distinct_count -= 1
                left += 1

            # Every suffix of nums[left : right + 1] ending at `right` is valid.
            subarray_count += right - left + 1

        return subarray_count

Interview follow-ups

Why is it difficult to count exactly k distinct values with one window?

A single window can identify whether its current range has exactly k distinct values, but that does not reveal how many valid starting positions share the same right edge. Moving the left edge past repeated values may preserve all k distinct values, creating several valid subarrays. Adding just one would undercount; moving left greedily risks destroying information needed for the next right edge.

The at-most formulation avoids that ambiguity. Once its longest valid window is known, every later start is guaranteed valid, so the number of valid starts has the simple closed form right - left + 1. Subtracting two such cumulative counts then isolates exactly k.

Can exactly k be counted in one pass instead of two helper calls?

Yes. Maintain two left boundaries for the same right edge: one window with at most k distinct values and another with at most k - 1. The difference between their left positions is the number of subarrays ending at that right edge with exactly k distinct values.

This still needs separate frequency state for the two windows and has the same O(n) time and O(d) space bounds. It saves one traversal but usually makes the implementation and invariant harder to explain. The two-helper version is often the better interview answer unless the interviewer explicitly asks for a single traversal.

What if array values are negative, strings, or other hashable objects?

The method does not rely on numeric ordering or sums. It tracks only equality and frequency, so negative integers work without any change. Strings or other hashable values work with a correspondingly typed frequency map.

Unlike sum-based sliding windows, distinct-count windows remain monotonic: adding an element can increase the distinct count by at most one, and removing an element can decrease it only when the last copy leaves. Hash-map operations are expected O(1); if hashing is unavailable or adversarial worst-case guarantees matter, coordinate compression followed by an array of counts gives deterministic indexing at an added O(n log n) preprocessing cost.

Can the frequency map be replaced with an array?

Yes, when values lie in a known compact range. Allocate a count array indexed by value, and update it exactly as the dictionary is updated. This removes hashing overhead and keeps the scan O(n).

The tradeoff is space proportional to the value range rather than the number of values actually present. If values are large or sparse, first coordinate-compress them into IDs from 0 through d - 1; sorting for compression costs O(n log n), after which the sliding window uses O(d) space.

How would the solution return every matching subarray rather than only the count?

Maintain the two at-most windows simultaneously. For each right edge, every start index from the at-most-k left boundary up to, but not including, the at-most-k - 1 left boundary forms a subarray with exactly k distinct values. Emit each corresponding (start, right) pair.

The window maintenance remains O(n), but producing r ranges takes O(r) additional time and output space, so the full complexity is O(n + r). That output-sensitive cost is unavoidable because the number of valid subarrays can be quadratic.

How would this change for a fixed window length?

Keep one window whose length never exceeds the requested size. Add the incoming value, remove the outgoing value when the window grows too long, and check the map size only when the window has the exact required length. Each right edge then represents at most one candidate subarray rather than many suffixes.

The result is still O(n) expected time and O(d) extra space. The at-most subtraction is unnecessary because the map directly tells whether that single fixed-length window has exactly k distinct values.

How should many different k queries on the same array be handled?

Running this algorithm independently for each query costs O(nq) time for q queries and is often the simplest choice. Results can be cached when query values repeat, and any k larger than the array’s total distinct count returns zero immediately.

There is no equally simple linear-time preprocessing that answers every exact-distinct query in constant time for an arbitrary array. More specialized offline algorithms can improve some workloads, but they are substantially more complex. In an interview, the right next step is to clarify the number of queries, array size, and whether preprocessing is allowed before choosing that tradeoff.