Leetcode 1852 Distinct Numbers in Each Subarray

Problem statement

https://leetcode.com/problems/distinct-numbers-in-each-subarray/

Solution

Keep counter of sliding window and when we add element and remove element, update counter and number of non-zero elements in counter.

Complexity

Time complexity is O(n) as well as space.

Code

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