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. Your task is to find the length of the shortest subarray that contains **exactly** $K$ distinct values. If no such subarray exists, return $-1$.
Your solution must run in $O(n)$ time. Design it using the two-window trick: express "exactly $K$ distinct" as the difference between two "at most $K
quot; sliding windows, and explain how you maintain element frequency counts as each window expands and contracts.
**Parts:**
1. Implement a helper `shortest_at_most(arr, k)` that returns the length of the shortest subarray with **at most** $k$ distinct values.
2. Use that helper to solve the original problem.
3. State the time and space complexity.
Loading problems...
Open the full interactive solver, hints, and worked solution →