Given an integer array `arr` and an integer `k`, find the **minimum length** of a contiguous subarray that contains **exactly `k` distinct** integer values. Return the minimum length, or `-1` if no such subarray exists. ```hint Where to start Think about a single pass with a **sliding window** plus a hash map from value → count inside the window. The number of map keys is the number of distinct values currently in the window. ``` ```hint The "exactly k" trap "At least `k` distinct" is the easy variant. For **exactly `k`**, once the window holds `k` distinct values, keep shrinking from the left: you can safely drop the leftmost element as long as it's a *duplicate* (its count in the window stays $\geq 1$ after removal). Stop shrinking the moment removing the left element would drop a distinct value (count would hit $0$), then record the window length. ``` ```hint Pitfall When you grow the window and the distinct count exceeds `k`, that window can never be salvaged by adding more elements — you must advance the left pointer until distinct $\leq k$ again. Don't measure length while distinct is $\neq k$. ``` ### Constraints & Assumptions - `arr` can contain duplicate values; values may be any integers (positive, negative, or zero). - A *subarray* is a **contiguous** slice of the array — not a subsequence. - "Exactly `k` distinct" means the set of distinct values inside the window has cardinality exactly `k`. - Aim for $O(n)$ time and $O(n)$ extra space, where $n$ is the length of `arr`. ### Clarifying Questions to Ask - What should be returned when `k = 0` or when `k` exceeds the total number of distinct values in `arr`? (Likely `-1`, since no qualifying subarray exists.) - Can `arr` be empty? What is the expected return in that case? - Is `k` guaranteed to be non-negative, and can it be larger than `len(arr)`? - Should the answer count a single qualifying window, or is there any tie-breaking requirement beyond "minimum length"? ### What a Strong Answer Covers - **Correct distinction between "exactly k" and "at most/at least k" distinct** — and an algorithm that shrinks the window only on duplicates so it lands on the *minimum* exactly-`k` window. - A clean **sliding-window + frequency-map** implementation that is a single left-to-right pass, $O(n)$ time. - Correct **window-shrink logic**: removing left elements while their in-window count stays positive, stopping before dropping a distinct value, and recording the length only when distinct count equals `k`. - **Edge cases**: no qualifying subarray (return `-1`), `k = 0`, `k` greater than the array's distinct count, empty array, all-equal elements. - A clear statement of **time and space complexity** and why the window pointers each move at most $n$ times (amortized linear). ### Follow-up Questions - How would you adapt the solution to return the **count of all** subarrays with exactly `k` distinct integers, rather than the minimum length? (Hint: `exactly(k) = atMost(k) − atMost(k−1)`.) - If you instead needed the **maximum length** subarray with exactly `k` distinct, how would the shrink condition change? - Suppose the array is a **stream** you can only read once and cannot store fully — what part of this approach breaks, and what would you do? - How would you handle the variant "exactly `k` distinct **and** every value appears at least `m` times"?