##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1852.html

# 1852. Distinct Numbers in Each Subarray

Medium

## Description

Given an integer array nums and an integer k, you are asked to construct the array ans of size n-k+1 where ans[i] is the number of distinct numbers in the subarray nums[i:i+k-1] = [nums[i], nums[i+1], ..., nums[i+k-1]].

Return the array ans.

Example 1:

Input: nums = [1,2,3,2,2,1,3], k = 3

Output: [3,2,2,2,3]

Explanation: The number of distinct elements in each subarray goes as follows:

• nums[0:2] = [1,2,3] so ans[0] = 3
• nums[1:3] = [2,3,2] so ans[1] = 2
• nums[2:4] = [3,2,2] so ans[2] = 2
• nums[3:5] = [2,2,1] so ans[3] = 2
• nums[4:6] = [2,1,3] so ans[4] = 3

Example 2:

Input: nums = [1,1,1,1,2,3,4], k = 4

Output: [1,2,3,4]

Explanation: The number of distinct elements in each subarray goes as follows:

• nums[0:3] = [1,1,1,1] so ans[0] = 1
• nums[1:4] = [1,1,1,2] so ans[1] = 2
• nums[2:5] = [1,1,2,3] so ans[2] = 3
• nums[3:6] = [1,2,3,4] so ans[3] = 4

Constraints:

• 1 <= k <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

## Solution

Use a hash map to store each number’s occurrences in the sliding window. For each i from k - 1 to n - 1, the corresponding value in ans is the size of the map.

• class Solution {
public int[] distinctNumbers(int[] nums, int k) {
int n = nums.length;
int[] ans = new int[n - k + 1];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < k; i++) {
int num = nums[i];
map.put(num, map.getOrDefault(num, 0) + 1);
}
ans[0] = map.size();
for (int i = k; i < n; i++) {
int prev = nums[i - k], curr = nums[i];
map.put(prev, map.get(prev) - 1);
if (map.get(prev) == 0)
map.remove(prev);
map.put(curr, map.getOrDefault(curr, 0) + 1);
ans[i - k + 1] = map.size();
}
return ans;
}
}

############

class Solution {
public int[] distinctNumbers(int[] nums, int k) {
int[] cnt = new int[100010];
int x = 0;
for (int i = 0; i < k; ++i) {
if (cnt[nums[i]]++ == 0) {
++x;
}
}
int n = nums.length;
int[] ans = new int[n - k + 1];
ans[0] = x;
for (int i = k; i < n; ++i) {
if (--cnt[nums[i - k]] == 0) {
--x;
}
if (cnt[nums[i]]++ == 0) {
++x;
}
ans[i - k + 1] = x;
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/distinct-numbers-in-each-subarray/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<int> distinctNumbers(vector<int>& A, int k) {
unordered_map<int, int> cnt;
vector<int> ans(A.size() - k + 1);
for (int i = 0, N = A.size(); i < N; ++i) {
cnt[A[i]]++;
if (i - k >= 0 && --cnt[A[i - k]] == 0) cnt.erase(A[i - k]);
if (i >= k - 1) ans[i - k + 1] = cnt.size();
}
return ans;
}
};

• class Solution:
def distinctNumbers(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
cnt = Counter(nums[:k])
ans = [len(cnt)]
for i in range(k, n):
u = nums[i - k]
cnt[u] -= 1
if cnt[u] == 0:
cnt.pop(u)

cnt[nums[i]] += 1
ans.append(len(cnt))
return ans


• func distinctNumbers(nums []int, k int) []int {
cnt := map[int]int{}
for _, v := range nums[:k] {
cnt[v]++
}
ans := []int{len(cnt)}
for i := k; i < len(nums); i++ {
u := nums[i-k]
cnt[u]--
if cnt[u] == 0 {
delete(cnt, u)
}
cnt[nums[i]]++
ans = append(ans, len(cnt))
}
return ans
}

• function distinctNumbers(nums: number[], k: number): number[] {
const m = Math.max(...nums);
const cnt: number[] = Array(m + 1).fill(0);
let v: number = 0;
for (let i = 0; i < k; ++i) {
if (++cnt[nums[i]] === 1) {
v++;
}
}
const ans: number[] = [v];
for (let i = k; i < nums.length; ++i) {
if (++cnt[nums[i]] === 1) {
v++;
}
if (--cnt[nums[i - k]] === 0) {
v--;
}
ans.push(v);
}
return ans;
}