# 1852. Distinct Numbers in Each Subarray

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public: vector distinctNumbers(vector& nums, int k) { vector ans; int distinct = 0; unordered_map count; for (int i = 0; i < nums.size(); ++i) { if (++count[nums[i]] == 1) ++distinct; if (i >= k && --count[nums[i - k]] == 0) --distinct; if (i >= k - 1) ans.push_back(distinct); } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int[] distinctNumbers(int[] nums, int k) { int[] ans = new int[nums.length - k + 1]; int distinct = 0; Map count = new HashMap<>(); for (int i = 0; i < nums.length; ++i) { if (count.merge(nums[i], 1, Integer::sum) == 1) ++distinct; if (i >= k && count.merge(nums[i - k], -1, Integer::sum) == 0) --distinct; if (i >= k - 1) ans[i - k + 1] = distinct; } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def distinctNumbers(self, nums: List[int], k: int) -> List[int]: ans = [] count = collections.Counter() distinct = 0 for i, num in enumerate(nums): count[num] += 1 if count[num] == 1: distinct += 1 if i >= k: count[nums[i - k]] -= 1 if count[nums[i - k]] == 0: distinct -= 1 if i >= k - 1: ans.append(distinct) return ans