Problem Description

You are given an array of integers nums and an integer k. Your task is to find, for every contiguous subarray of length k in nums, how many distinct numbers are present in that subarray.

Return an array result where result[i] is the number of distinct integers in the subarray nums[i:i+k].

• Each subarray must be of length k.
• The result should list the count for every possible subarray of length k (from index 0 to len(nums)-k).
• There is one valid answer for each subarray. Do not reuse elements across different subarrays.

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

Thought Process

At first glance, the problem looks like a sliding window problem. For each window of size k, we need to count how many different numbers are present. The brute-force way would be to, for each subarray, collect its elements and count the number of unique values (perhaps by converting to a set).

However, this brute-force approach would be slow for large arrays because it repeats a lot of work. Instead, we can optimize by noticing that as we "slide" the window to the right by one, only one number leaves the window and one new number enters. If we can efficiently keep track of the counts of each number in the current window, we can update the number of distinct elements in constant time per step.

This is a classic use-case for a hash map (dictionary): we can store the frequency of each number in the current window. When a number leaves, we decrement its count (and if its count drops to zero, it is no longer present). When a new number enters, we increment its count. The number of keys in the map with count > 0 gives us the number of distinct elements.

Solution Approach

Let's break down the optimized approach step by step:

1. Initialize a hash map (dictionary): This will store the count of each number currently in the window.
2. Process the first window: For the first k elements, add each to the hash map and track the number of unique keys (distinct numbers).
3. Slide the window: For each subsequent index:
   • Remove the element going out of the window (leftmost). Decrease its count in the hash map. If its count becomes zero, remove it from the map (since it's no longer in the window).
   • Add the new element coming into the window (rightmost). Increase its count in the hash map. If it wasn't already present, it adds to the count of distinct numbers.
   • Append the current number of distinct keys to the result list.
4. Return the result: After processing all windows, return the result list.

This approach ensures that each element is added and removed from the hash map at most once per window, making the algorithm efficient.

Example Walkthrough

Let's use the example nums = [1,2,3,2,2,1,3] and k = 3.

1. First window (indices 0-2): [1,2,3]
   Distinct numbers: 1, 2, 3 → count = 3
2. Next window (indices 1-3): [2,3,2]
   Remove 1 (count becomes 0, remove from map), add 2 (count increases to 2). Distinct numbers: 2, 3 → count = 2
3. Next window (indices 2-4): [3,2,2]
   Remove 2 (count decreases to 1), add 2 (count increases to 2). Distinct numbers: 2, 3 → count = 2
4. Next window (indices 3-5): [2,2,1]
   Remove 3 (count becomes 0, remove from map), add 1 (count increases to 1). Distinct numbers: 2, 1 → count = 2
5. Next window (indices 4-6): [2,1,3]
   Remove 2 (count decreases to 1), add 3 (count increases to 1). Distinct numbers: 2, 1, 3 → count = 3
   But actually, in the code above, the last window should be [2,1,3], but the sample output is [3,2,2,2,2]. Let's check the process:
   • Window 1: [1,2,3] → 3
   • Window 2: [2,3,2] → 2
   • Window 3: [3,2,2] → 2
   • Window 4: [2,2,1] → 2
   • Window 5: [2,1,3] → 3
   Actually, the sample output in the problem description is [3,2,2,2,2], which suggests the last window is [2,2,1]. But the correct process (as per the usual problem) is to process all windows of size k.
   For each step, we efficiently update the map and count the number of distinct elements.

Time and Space Complexity

• Brute-force approach: For each window of size k, create a set of its elements to count distinct numbers. There are n-k+1 windows, and each set operation takes up to O(k) time, so total time is O((n-k+1) * k).
• Optimized approach: We slide the window over the array, and each add/remove operation in the hash map is O(1) (on average). Each element is added and removed at most once, so total time is O(n).
• Space complexity: At most, the hash map stores up to k different numbers (if all are unique in a window), so space is O(k).

Summary

The problem of finding the number of distinct numbers in each sliding window of size k can be solved efficiently using a sliding window and a hash map to keep track of element counts. By updating the counts as we move the window, we avoid redundant work and achieve linear time complexity. This approach is both elegant and practical, making it suitable for large input sizes.

Code Implementation

from collections import defaultdict
def distinctNumbers(nums, k):
    result = []
    count = defaultdict(int)
    distinct = 0

    for i in range(len(nums)):
        count[nums[i]] += 1
        if count[nums[i]] == 1:
            distinct += 1
        if i >= k:
            count[nums[i - k]] -= 1
            if count[nums[i - k]] == 0:
                distinct -= 1
        if i >= k - 1:
            result.append(distinct)
    return result
      

#include <vector>
#include <unordered_map>
using namespace std;

vector<int> distinctNumbers(vector<int>& nums, int k) {
    vector<int> result;
    unordered_map<int, int> count;
    int distinct = 0;
    for (int i = 0; i < nums.size(); ++i) {
        count[nums[i]]++;
        if (count[nums[i]] == 1) distinct++;
        if (i >= k) {
            count[nums[i - k]]--;
            if (count[nums[i - k]] == 0) distinct--;
        }
        if (i >= k - 1) result.push_back(distinct);
    }
    return result;
}
      

import java.util.*;

public class Solution {
    public List<Integer> distinctNumbers(int[] nums, int k) {
        List<Integer> result = new ArrayList<>();
        Map<Integer, Integer> count = new HashMap<>();
        int distinct = 0;
        for (int i = 0; i < nums.length; ++i) {
            count.put(nums[i], count.getOrDefault(nums[i], 0) + 1);
            if (count.get(nums[i]) == 1) distinct++;
            if (i >= k) {
                count.put(nums[i - k], count.get(nums[i - k]) - 1);
                if (count.get(nums[i - k]) == 0) distinct--;
            }
            if (i >= k - 1) result.add(distinct);
        }
        return result;
    }
}
      

function distinctNumbers(nums, k) {
    let result = [];
    let count = new Map();
    let distinct = 0;
    for (let i = 0; i < nums.length; ++i) {
        count.set(nums[i], (count.get(nums[i]) || 0) + 1);
        if (count.get(nums[i]) === 1) distinct++;
        if (i >= k) {
            count.set(nums[i - k], count.get(nums[i - k]) - 1);
            if (count.get(nums[i - k]) === 0) distinct--;
        }
        if (i >= k - 1) result.push(distinct);
    }
    return result;
}