Problem

You are given an integer array nums of length n and an integer k. Your task is to find the number of distinct elements in every subarray of size k within nums.

Return an array ans such that ans[i] is the count of distinct elements in nums[i..(i + k - 1)] for each index 0 <= i < n - k.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6
7

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

Method 1 – Sliding Window with Hash Map

Intuition

To efficiently count distinct elements in every subarray of size k, we can use a sliding window and a hash map to track the frequency of each element. As the window moves, we add the new element and remove the old one, updating the count of distinct elements in constant time.

Approach

  1. Initialize a hash map to store the frequency of elements in the current window.
  2. Iterate through the array, adding the current element to the map and increasing its count.
  3. When the window size exceeds k, remove the element that is sliding out and update its count in the map.
  4. After the first k-1 elements, record the number of keys in the map (distinct elements) for each window.
  5. Continue until the end of the array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    vector<int> distinctNumbers(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        vector<int> ans;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            cnt[nums[i]]++;
            if (i >= k) {
                if (--cnt[nums[i - k]] == 0) cnt.erase(nums[i - k]);
            }
            if (i >= k - 1) ans.push_back(cnt.size());
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func distinctNumbers(nums []int, k int) []int {
    cnt := map[int]int{}
    ans := []int{}
    for i, v := range nums {
        cnt[v]++
        if i >= k {
            cnt[nums[i-k]]--
            if cnt[nums[i-k]] == 0 {
                delete(cnt, nums[i-k])
            }
        }
        if i >= k-1 {
            ans = append(ans, len(cnt))
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int[] distinctNumbers(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        for (int i = 0; i < n; ++i) {
            cnt.put(nums[i], cnt.getOrDefault(nums[i], 0) + 1);
            if (i >= k) {
                int out = nums[i - k];
                cnt.put(out, cnt.get(out) - 1);
                if (cnt.get(out) == 0) cnt.remove(out);
            }
            if (i >= k - 1) ans[i - k + 1] = cnt.size();
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun distinctNumbers(nums: IntArray, k: Int): IntArray {
        val cnt = mutableMapOf<Int, Int>()
        val ans = mutableListOf<Int>()
        for (i in nums.indices) {
            cnt[nums[i]] = cnt.getOrDefault(nums[i], 0) + 1
            if (i >= k) {
                val out = nums[i - k]
                cnt[out] = cnt[out]!! - 1
                if (cnt[out] == 0) cnt.remove(out)
            }
            if (i >= k - 1) ans.add(cnt.size)
        }
        return ans.toIntArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

impl Solution {
    pub fn distinct_numbers(nums: Vec<i32>, k: i32) -> Vec<i32> {
        use std::collections::HashMap;
        let mut cnt = HashMap::new();
        let mut ans = Vec::new();
        let k = k as usize;
        for (i, &v) in nums.iter().enumerate() {
            *cnt.entry(v).or_insert(0) += 1;
            if i >= k {
                let out = nums[i - k];
                let e = cnt.get_mut(&out).unwrap();
                *e -= 1;
                if *e == 0 {
                    cnt.remove(&out);
                }
            }
            if i + 1 >= k {
                ans.push(cnt.len() as i32);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    distinctNumbers(nums: number[], k: number): number[] {
        const cnt = new Map<number, number>();
        const ans: number[] = [];
        for (let i = 0; i < nums.length; ++i) {
            cnt.set(nums[i], (cnt.get(nums[i]) || 0) + 1);
            if (i >= k) {
                const out = nums[i - k];
                cnt.set(out, cnt.get(out)! - 1);
                if (cnt.get(out) === 0) cnt.delete(out);
            }
            if (i >= k - 1) ans.push(cnt.size);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), since each element is added and removed from the map at most once.
  • 🧺 Space complexity: O(k), for the hash map storing up to k elements at a time.