Shortest Subarray with Exactly K Distinct Values
You are given an array $a_1, a_2, \\ldots, a_n$ of integers and a positive integer $K$. A subarray is a contiguous slice of the array. Find the length of the shortest subarray that contains exactly $K$ distinct values. If no such subarray exists, return $-1$.
Implement the function:
```python def shortest_exactly_k(arr, K): ... ```
It must return an int (the length), or -1 when no qualifying subarray exists. Aim for $O(n)$ time using the two-window trick: express "exactly $K$ distinct" as the gap between an "at most $K$" window and an "at most $K-1$" window, maintaining element frequency counts as each window expands and contracts.
Example
shortest_exactly_k([1, 2, 1, 3, 4], 3) -> 3
The shortest subarray with exactly 3 distinct values is length 3 (e.g. [2, 1, 3] or [1, 3, 4]); no shorter window reaches 3 distinct values.
Hints
- "Exactly $K$ distinct" is hard to handle directly with a single sliding window -- think about how to express it as a difference of two easier conditions.
- A subarray has exactly $K$ distinct values if and only if it satisfies "at most $K$" but not "at most $K-1$". For each right endpoint $r$, the valid left endpoints for these two conditions give you a range -- the shortest valid window ending at $r$ is the right end of that range.
- Run two left pointers simultaneously:
left_k(shrinks until the window has $\leq K$ distinct) andleft_k1(shrinks until $\leq K-1$ distinct). For each $r$, the shortest exactly-$K$ window ending at $r$ has length $r - \text{left\_k1} + 1$. Maintain frequency maps for each pointer independently.
Worked Solution
How to Think About It: The word "exactly" is what makes this tricky. Sliding windows naturally handle inequalities ("at most K distinct"): expand the right edge, and shrink the left edge whenever the constraint is violated. "Exactly K" is both a lower and an upper bound at once. The key trick is to run two windows sharing the same right endpoint:
- one kept at at most K distinct (left pointer
left_k), - one kept at at most K-1 distinct (left pointer
left_k1).
For a subarray ending at right, the number of distinct values is non-increasing as the left endpoint moves rightward. So the left endpoints giving *exactly* K distinct form the contiguous range [left_k, left_k1 - 1]. The shortest window ending at right uses the largest valid left, left_k1 - 1, giving length right - (left_k1 - 1) + 1. Both pointers advance monotonically, so it is a single O(n) pass.
Function signature: shortest_exactly_k(arr, K) returns an int — the length of the shortest contiguous subarray of arr with exactly K distinct values, or -1 if none exists.
Code:
```python from collections import defaultdict
def shortest_exactly_k(arr, K): # Length of the shortest contiguous subarray with EXACTLY K distinct # values, or -1 if none exists. n = len(arr) if n == 0 or K <= 0: return -1
# Two simultaneous sliding windows sharing the same right endpoint: # left_k keeps the window at "at most K" distinct. # left_k1 keeps the window at "at most K-1" distinct. # For a window ending at right to have EXACTLY K distinct, its left # endpoint must sit in [left_k, left_k1 - 1]. The shortest such window # takes the largest valid left = left_k1 - 1. left_k = 0 left_k1 = 0 count_k = defaultdict(int) count_k1 = defaultdict(int) ans = float('inf')
for right in range(n): val = arr[right] count_k[val] += 1 count_k1[val] += 1
while len(count_k) > K: out = arr[left_k] count_k[out] -= 1 if count_k[out] == 0: del count_k[out] left_k += 1
while len(count_k1) > K - 1: out = arr[left_k1] count_k1[out] -= 1 if count_k1[out] == 0: del count_k1[out] left_k1 += 1
# Exactly-K window exists iff the "at most K" window truly holds K # distinct and there is room between the two left pointers. if len(count_k) == K and left_k1 - 1 >= left_k: ans = min(ans, right - (left_k1 - 1) + 1)
return ans if ans < float('inf') else -1 ```
Complexity:
- Time: O(n) — each element enters and leaves each frequency map at most once, so all pointer motion amortizes to O(n).
- Space: O(K) — each frequency map holds at most K distinct keys.
Intuition
The core insight here is the "at most" decomposition: problems asking for a sliding window with an exact count are almost always easier to solve by taking the difference of two "at most" windows. This pattern appears constantly -- exactly $K$ occurrences, exactly $K$ unique characters, exactly $K$ odd numbers. Once you see it, the implementation is mechanical: two independent left pointers, two frequency maps, one right pointer sweep.
In practice, frequency maps in sliding windows are a staple of streaming data problems. On a trading desk you might track the number of distinct counterparties, securities, or venues active in a rolling time window -- the same shrink-and-expand logic applies. The amortized $O(n)$ bound comes from the fact that each element enters and leaves each window at most once, regardless of how many times the window shrinks. Recognizing that amortization argument -- and being able to state it clearly -- is what separates a clean interview answer from a hand-wavy one.