Distinct Numbers in Each Subarray

Problem Statement

In this task, we have an array of integers named nums with size n and an integer k. Our goal is to determine the count of distinct elements for every subarray of length k within the array nums. For each such subarray, the total number of unique elements is calculated and stored in a result array ans. The array ans[i] will represent the number of unique elements for the subarray starting from index i to i+k-1. This process continues until we have considered all possible subarrays of length k that can be formed from the array nums.

Examples

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 <= 105
• 1 <= nums[i] <= 105

Approach and Intuition

Given the problem, our target is to efficiently compute the number of distinct elements for every possible subarray of size k. Let's go through the approach to solve this:

1. Initialize a Window: Start with a sliding window of size k which initially covers the segment nums[0..(k-1)].

2. Use a Dictionary to Count Elements: Utilize a dictionary (hash map) to maintain a count of each element in the current window. The keys in the dictionary are the elements, and the values are their respective counts in the current window.

3. Calculate Distinct Count for First Window: For the initial window, traverse through each element in nums[0..(k-1)], updating the element counts in the dictionary. The number of keys in the dictionary after processing this window will be the answer for the first position in ans.

4. Slide the Window: Move the window one index to the right. This involves decreasing the count of the element that is left behind (the one that slides out of the window) and increasing the count of the new element that enters the window.

5. Update Dictionary and Result for Each New Window Position: Adjust the dictionary according to the element that leaves the window and the one that enters. If the count of an element reaches zero, it should be removed from the dictionary to keep the dictionary clean and efficient. The new length of the dictionary keys gives the count of distinct elements for the current window position. Store this value in ans.

6. Repeat Until the End of the Array: Continue sliding the window and updating counts until the window reaches the end of nums.

This efficient approach ensures that each element is processed only twice (once when it enters the window and once when it exits), leading to O(n) complexity, which is optimal given the constraints. By maintaining a dynamic count of elements within the current window, the algorithm efficiently calculates the number of distinct elements for each position without having to repeatedly count distinct elements from scratch for each window.

Solutions

class Solution {
public:
    vector<int> uniqueNumbers(vector<int>& data, int windowSize) {
        int highestValue = 0;
        for (int value : data) {
            if (value > highestValue) {
                highestValue = value;
            }
        }
    
        vector<int> frequency(highestValue + 1, 0);
        int uniqueCount = 0;
        vector<int> result;
    
        for (int index = 0; index < data.size(); index++) {
            frequency[data[index]]++;
            if (frequency[data[index]] == 1) {
                uniqueCount++;
            }
    
            if (index >= windowSize) {
                frequency[data[index - windowSize]]--;
                if (frequency[data[index - windowSize]] == 0) {
                    uniqueCount--;
                }
            }
    
            if (index + 1 >= windowSize) {
                result.push_back(uniqueCount);
            }
        }
    
        return result;
    }
};