A ride log records the zone id of every pickup, in order. Analysts want the shortest run of consecutive pickups that touches at least k different zones.
Implement shortest_k_distinct(arr: list[int], k: int) -> int: the length of the shortest contiguous subarray of arr containing at least k distinct values, or -1 if no subarray does (that is, if arr as a whole has fewer than k distinct values).
shortest_k_distinct([4, 4, 2, 4, 7, 2], 3) # 3 [2, 4, 7]
shortest_k_distinct([5, 5, 5], 1) # 1
shortest_k_distinct([5, 5, 5], 2) # -1
shortest_k_distinct([1, 2, 1, 1, 3], 3) # 4 [2, 1, 1, 3]
In the last example every window with 3 distinct values must reach from the 2 (index 1) to the 3 (index 4), repeated 1s and all.
Constraints: 1 <= len(arr) <= 100,000, 1 <= arr[i] <= 100,000, 1 <= k <= len(arr). Checking every subarray is O(n²) and too slow.
Show hint
Slide a window with a value -> count dict. Extend the right end one step at a time; whenever the window has at least k distinct values, record its length and shrink it from the left for as long as that stays true.