Find Numbers with Unique Elements in K-Sized Windows in Python

Suppose we have a list of numbers called nums and another number k, we have to find a list of count of distinct numbers in each window of size k.

So, if the input is like nums = [2, 2, 3, 3, 4], k = 2, then the output will be [1, 2, 1, 2], as the windows are [2, 2], [2, 3], [3, 3], and [3, 4].

To solve this, we will follow these steps −

• c := make a dictionary of elements in nums and their frequencies

• ans := a new list

• for i in range k to size of nums, do

  • insert size of c at the end of ans

  • c[nums[i]] := c[nums[i]] + 1

  • c[nums[i - k]] := c[nums[i - k]] - 1

  • if c[nums[i - k]] is same as 0, then

    • remove c[nums[i - k]]

• insert size of c at the end of ans

• return ans

Let us see the following implementation to get better understanding −

Example

 Live Demo

from collections import Counter

class Solution:
   def solve(self, nums, k):
      c = Counter()
      for i in range(k):
         c[nums[i]] += 1
      ans = []
      for i in range(k, len(nums)):
         ans.append(len(c))
         c[nums[i]] += 1
         c[nums[i - k]] -= 1
         if c[nums[i - k]] == 0:
            del c[nums[i - k]]
      ans.append(len(c))
      return ans

ob = Solution()
nums = [2, 2, 3, 3, 4]
print(ob.solve(nums, 2))

Input

[2, 2, 3, 3, 4], 2

Output

[1, 2, 1, 2]