Count distinct values in every sliding window

Given an integer array nums and a window size k, return a list with one entry per contiguous window of length k (there are len(nums) - k + 1 of them). Each entry is the number of different values inside that window.

Implement:

def count_distinct_in_windows(nums: list[int], k: int) -> list[int]: ...

Constraints

• 1 <= k <= len(nums) <= 10^5
• Values can be any integers: negative, zero, or positive.
• Aim for better than O(n * k) time.

Example 1

nums = [4, 4, 7, 2, 7, 4, 9], k = 3
output: [2, 3, 2, 3, 3]

The windows are [4,4,7], [4,7,2], [7,2,7], [2,7,4], [7,4,9].

Example 2

nums = [-1, 0, -1, 0, 1], k = 2
output: [2, 2, 2, 2]