Skip to content

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<int> distinctNumbers(vector<int>& nums, int k) {
    vector<int> ans;
    int distinct = 0;
    unordered_map<int, int> 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<Integer, Integer> 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