BinarySearch 0498 K Distinct Window

Problem statement

https://binarysearch.com/problems/K-Distinct-Window/

Solution

Use counter to keep frequencies of values. Use sliding window where we add and remove elements and update len of counter.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums, k):
        cnt, n = Counter(nums[:k]), len(nums)
        ans = [len(cnt)]
        for i in range(k, n):
            ans += [ans[-1]]
            cnt[nums[i]] += 1
            if cnt[nums[i]] == 1: ans[-1] += 1
            cnt[nums[i - k]] -= 1
            if cnt[nums[i - k]] == 0: ans[-1] -= 1

        return ans