K Distinct Window Algorithm by Sliding Window

Given a list of integers nums and an integer k, return a list of count of distinct numbers in each window of size k.

Constraints
1 ≤ k ≤ n ≤ 100,000 where n is length of nums.
Example 1
Input
nums = [1, 1, 2, 2, 3]
k = 2
Output
[1, 2, 1, 2]
Explanation
The windows are [1, 1], [1, 2], [2, 2], and [2, 3].

Slding Window Algorithm to Compute the K Distinct Window

We can use a sliding window which keeps the size of the distinct window. If the number of the distinct window is more than K, we move the left pointer.

vector<int> kDistinctWindow(vector<int>& nums, int k) {
    int n = nums.size();
    if (0 == n) return {};
    vector<int> res;
    unordered_map<int, int> w;
    for (int i = 0; i < n; ++ i) {
        w[nums[i]] ++;
        if (i >= k) {
            if (--w[nums[i - k]] == 0) {
                w.erase(nums[i - k]);
            }
        }
        if (i >= k - 1) {
            res.push_back(w.size());
        }
    }
    return res;
}

The time complexity is O(N) and the space complexity is O(N) where N is the number of elements in the array.

–EOF (The Ultimate Computing & Technology Blog) —