Leetcode 1852. Distinct Numbers in Each Subarray

Problem 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.

Let's go through the provided example:

Example:

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

We can understand the problem by breaking down each step:

• 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

Solution Approach

The solution uses a sliding window approach, with the help of a hashtable to store the count of each distinct element in the current window of size k. Whenever we move the window to the next position, we update the hashtable by incrementing the count of the new element and decrementing the count of the removed element from the window.

Let's go through the solution step by step with the given example:

1nums = [1,2,3,2,2,1,3], k = 3
2ans = []
3
4Step 1:
5  - window: [1,2,3]
6  - hashtable: {1: 1, 2: 1, 3: 1}
7  - ans: [3]
8
9Step 2:
10  - window: [2,3,2]
11  - hashtable: {1: 0, 2: 2, 3: 1}
12  - ans: [3, 2]
13
14Step 3:
15  - window: [3,2,2]
16  - hashtable: {1: 0, 2: 2, 3: 1}
17  - ans: [3, 2, 2]
18
19Step 4:
20  - window: [2,2,1]
21  - hashtable: {1: 1, 2: 2, 3: 0}
22  - ans: [3, 2, 2, 2]
23
24Step 5:
25  - window: [2,1,3]
26  - hashtable: {1: 1, 2: 1, 3: 1}
27  - ans: [3, 2, 2, 2, 3]

C++ Solution

1#include <vector>
2#include <unordered_map>
3
4class Solution {
5public:
6    std::vector<int> distinctNumbers(std::vector<int>& nums, int k) {
7        std::vector<int> ans;
8        int distinct = 0;
9        std::unordered_map<int, int> count;
10
11        for (int i = 0; i < nums.size(); ++i) {
12            if (++count[nums[i]] == 1)
13                ++distinct;
14            if (i >= k && --count[nums[i - k]] == 0)
15                --distinct;
16            if (i >= k - 1)
17                ans.push_back(distinct);
18        }
19
20        return ans;
21    }
22};

Python Solution

1from collections import defaultdict
2
3class Solution:
4    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:
5        ans = []
6        distinct = 0
7        count = defaultdict(int)
8
9        for i in range(len(nums)):
10            count[nums[i]] += 1
11            if count[nums[i]] == 1:
12                distinct += 1
13                
14            if i >= k:
15                count[nums[i - k]] -= 1
16                if count[nums[i - k]] == 0:
17                    distinct -= 1
18                    
19            if i >= k - 1:
20                ans.append(distinct)
21
22        return ans

Java Solution

1import java.util.HashMap;
2import java.util.ArrayList;
3import java.util.List;
4
5class Solution {
6    public List<Integer> distinctNumbers(int[] nums, int k) {
7        List<Integer> ans = new ArrayList<>();
8        int distinct = 0;
9        HashMap<Integer, Integer> count = new HashMap<>();
10
11        for (int i = 0; i < nums.length; ++i) {
12            count.put(nums[i], count.getOrDefault(nums[i], 0) + 1);
13            if (count.get(nums[i]) == 1)
14                ++distinct;
15            if (i >= k && count.put(nums[i - k], count.get(nums[i - k]) - 1) == 1)
16                --distinct;
17            if (i >= k - 1)
18                ans.add(distinct);
19        }
20
21        return ans;
22    }
23}

C# Solution

1using System.Collections.Generic;
2
3public class Solution {
4    public IList<int> DistinctNumbers(int[] nums, int k) {
5        List<int> ans = new List<int>();
6        int distinct = 0;
7        Dictionary<int, int> count = new Dictionary<int, int>();
8
9        for (int i = 0; i < nums.Length; ++i) {
10            if (!count.ContainsKey(nums[i])) {
11                count[nums[i]] = 0;
12            }
13            count[nums[i]] += 1;
14            if (count[nums[i]] == 1) {
15                distinct++;
16            }
17            if (i >= k && --count[nums[i - k]] == 0) {
18                distinct--;
19            }
20            if (i >= k - 1) {
21                ans.Add(distinct);
22            }
23        }
24
25        return ans;
26    }
27}

JavaScript Solution

1class Solution {
2    distinctNumbers(nums, k) {
3        const ans = [];
4        let distinct = 0;
5        const count = new Map();
6
7        for (let i = 0; i < nums.length; ++i) {
8            count.set(nums[i], (count.get(nums[i]) || 0) + 1);
9
10            if (count.get(nums[i]) === 1) {
11                distinct++;
12            }
13
14            if (i >= k && count.set(nums[i - k], count.get(nums[i - k]) - 1).get(nums[i - k]) === 0) {
15                distinct--;
16            }
17
18            if (i >= k - 1) {
19                ans.push(distinct);
20            }
21        }
22
23        return ans;
24    }
25}
26```## Conclusion
27
28In this article, we have discussed the problem of counting the distinct elements of subarrays as well as the sliding window approach to solve it efficiently. We have provided the solution implementations in C++, Python, Java, C#, and JavaScript.