Shortest subarray with at least k distinct values

You are given an integer array arr and an integer k. Call a contiguous subarray good if it contains at least k different values.

Return the length of the shortest good subarray. If no subarray is good, return -1.

Implement:

def shortest_good_subarray(arr: list[int], k: int) -> int: ...

Constraints

• 1 <= len(arr) <= 10^5
• 1 <= arr[i] <= 10^5
• 1 <= k <= len(arr)

Example 1

arr = [4, 4, 7, 4, 9, 7], k = 3
output: 3

The window [4, 9, 7] holds three different values. No window of length 2 can.

Example 2

arr = [5, 5, 5], k = 2
output: -1

The array has only one distinct value, so no subarray is good.

Aim for a solution faster than checking every subarray.