050. Count Subarrays with Exactly K Distinct

Why this mechanism works

Exactly-k validity is awkward to preserve directly, but at-most-k is monotone under removing values. Every interval counted by atMost(k) but not by atMost(k-1) has exactly k distinct values. For each repaired at-most window ending at right, every start from left through right is valid, contributing right-left+1 intervals.

State and boundaries

The helper's counts represent the active window. left is its earliest valid start after repair. total counts all valid intervals by their right endpoint.

Protocol

1. Define an at-most helper.
2. Expand and shrink until the distinct count fits the limit.
3. Add the number of valid suffixes ending here.
4. Compute atMost(k)-atMost(k-1).

Visualization

atMost(2) intervals
  minus atMost(1) intervals
  equals exactly two distinct
valid starts for fixed right: left..right

Python implementation

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

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 subarrays_exactly_k: def at_most(limit):
nums=[1, 2, 1, 2, 3]; k=2

L3 at_most: if limit <= 0:
limit=2; nums=[1, 2, 1, 2, 3]

L5 at_most: counts = {}
limit=2; nums=[1, 2, 1, 2, 3]; counts={}

L6 at_most: left = total = 0
limit=2; nums=[1, 2, 1, 2, 3]; counts={}; left=0; total=0

L7 at_most: for right, value in enumerate(nums):
limit=2; nums=[1, 2, 1, 2, 3]; counts={}; left=0; total=0; right=0; value=1

L8 at_most: counts[value] = counts.get(value, 0) + 1
limit=2; nums=[1, 2, 1, 2, 3]; counts={1:1}; left=0; total=0; right=0; value=1

L15 at_most: total += right - left + 1
limit=2; nums=[1, 2, 1, 2, 3]; counts={1:1}; left=0; total=1; right=0; value=1

L7 at_most: for right, value in enumerate(nums):
limit=2; nums=[1, 2, 1, 2, 3]; counts={1:1}; left=0; total=1; right=1; value=2

... 51 intermediate state changes omitted ...

L11 at_most: counts[old] -= 1
limit=1; nums=[1, 2, 1, 2, 3]; counts={2:0, 3:1}; left=3; total=4; right=4; value=3; old=2

L13 at_most: del counts[old]
limit=1; nums=[1, 2, 1, 2, 3]; counts={3:1}; left=3; total=4; right=4; value=3; old=2

L14 at_most: left += 1
limit=1; nums=[1, 2, 1, 2, 3]; counts={3:1}; left=4; total=4; right=4; value=3; old=2

L15 at_most: total += right - left + 1
limit=1; nums=[1, 2, 1, 2, 3]; counts={3:1}; left=4; total=5; right=4; value=3; old=2

L2 subarrays_exactly_k: def at_most(limit):
nums=[1, 1]; k=1

L3 at_most: if limit <= 0:
limit=1; nums=[1, 1]

L5 at_most: counts = {}
limit=1; nums=[1, 1]; counts={}

L6 at_most: left = total = 0
limit=1; nums=[1, 1]; counts={}; left=0; total=0

L7 at_most: for right, value in enumerate(nums):
limit=1; nums=[1, 1]; counts={}; left=0; total=0; right=0; value=1

L8 at_most: counts[value] = counts.get(value, 0) + 1
limit=1; nums=[1, 1]; counts={1:1}; left=0; total=0; right=0; value=1

L15 at_most: total += right - left + 1
limit=1; nums=[1, 1]; counts={1:1}; left=0; total=1; right=0; value=1

L7 at_most: for right, value in enumerate(nums):
limit=1; nums=[1, 1]; counts={1:1}; left=0; total=1; right=1; value=1

L8 at_most: counts[value] = counts.get(value, 0) + 1
limit=1; nums=[1, 1]; counts={1:2}; left=0; total=1; right=1; value=1

L15 at_most: total += right - left + 1
limit=1; nums=[1, 1]; counts={1:2}; left=0; total=3; right=1; value=1

L3 at_most: if limit <= 0:
limit=0; nums=[1, 1]

Why the solution is correct

All suffixes of an at-most window remain valid, while starts before the minimal repaired left boundary are invalid for this endpoint. Thus the helper counts each qualifying interval once. Subtracting the nested sets leaves exactly those with k distinct values.

Time and space

O(n) expected time across two scans and O(u) auxiliary space.

Common mistakes

Adding one per window counts endpoints rather than all valid intervals. The zero or negative limit must return zero without entering a repair loop that cannot become valid.

Reasoning card

Transfer exercise

Use the same difference-of-at-most idea to count binary subarrays with an exact number of ones.