Distinct Numbers in Each Subarray of Size K

109
0

Given an integer array nums and an integer k, count the distinct numbers in every group of k consecutive elements.

Return these counts in an array, following the groups from left to right. Repeated values count only once within each group.

Example 1

Input: nums = [4, 4, 2, 5, 2, 6], k = 3
Output: [2, 3, 2, 3]
Explanation: The groups [4, 4, 2], [4, 2, 5], [2, 5, 2], and [5, 2, 6] contain 2, 3, 2, 3 distinct numbers, respectively.

Example 2

Input: nums = [8, 8, 8, 8], k = 2
Output: [1, 1, 1]
Explanation: Each group of two consecutive elements contains only the distinct value 8.

Brute Force Approach

Each group of k consecutive elements is called a window. Within a window, a number must be counted only once, even if it appears several times. A set handles this naturally because it stores each different value only once. After inserting all the window’s elements into a set, the set’s size gives the distinct count.

Treat every window separately. Start with an empty set, collect the values from the current window, and record how many different values were collected. Then move the window forward by one position and repeat with a fresh set. Using a fresh set ensures that values belonging only to an earlier window do not affect the current count. Recording the counts from left to right produces the required result array.

Algorithm

  • Consider every valid window of k consecutive elements from left to right.

  • Create an empty set to store only the distinct elements for the current window.

  • Insert all k elements of that window into the set.

  • Add the set’s size to the result array.

  • Return the result after processing every window.

Dry Run

Distinct numbers in each subarray of size k - Brute

Distinct numbers in each subarray of size k - Brute

Solution

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the distinct count for each consecutive group of k elements.
vector<int> distinctNumbers(const vector<int>& nums, int k) {
int n = nums.size();
vector<int> result;
for (int start = 0; start <= n - k; start++) {
// Each window needs its own set of distinct values.
unordered_set<int> unique;
// Repeated insertions of the same value do not enlarge the set.
for (int i = start; i < start + k; i++) {
unique.insert(nums[i]);
}
// Save the count in the same order as the windows.
result.push_back(unique.size());
}
return result;
}
};
// Driver code
int main() {
vector<int> nums = {4, 4, 2, 5, 2, 6};
int k = 3;
// Create an instance of class Solution.
Solution sol;
vector<int> result = sol.distinctNumbers(nums, k);
// Print the returned counts in array format.
cout << "[";
for (int i = 0; i < result.size(); i++) {
if (i > 0) cout << ", ";
cout << result[i];
}
cout << "]\n";
return 0;
}

Complexity Analysis

Time Complexity: O((N - K + 1) × K) expected time, commonly written as O(N × K). Each window inserts K elements into a hash set, with expected constant time per insertion.

Space Complexity: O(K) auxiliary space for the current window’s set. The returned array uses an additional O(N - K) space.

Optimal Approach

Neighbouring windows share k - 1 elements, so moving forward changes only the outgoing element and the incoming element. A Hashmap allows the information about the shared elements to be reused. It stores each value together with the number of times that value appears in the current window.

When an element leaves, reduce its frequency by one. If its frequency is still positive, another copy remains in the window, so the value must still be counted as distinct. Remove the value from the map only when its frequency becomes zero. Then include the incoming element by increasing its frequency, creating a new entry if it was not already present.

After both updates, each remaining map entry represents exactly one distinct value in the new window. Therefore, the number of entries gives the required count. Build the map for the first window, record its size, and then update the same map as the window moves forward, recording one count after each move.

Algorithm

  • Count the occurrences or frequencies of each value in the first k elements using a Hashmap.

  • Add the number of map entries to the result array.

  • Move the window forward by removing one occurrence of the outgoing value.

  • If that value’s frequency becomes zero, remove its entry from the map.

  • Add one occurrence of the incoming value.

  • Record the number of map entries after both updates.

  • Repeat for all remaining windows and return the result array.

Dry Run

Distinct numbers in each subarray of size k - Optimal

Distinct numbers in each subarray of size k - Optimal

Solution

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the distinct count for each consecutive group of k elements.
vector<int> distinctNumbers(const vector<int>& nums, int k) {
unordered_map<int, int> frequency;
vector<int> result;
// Build the frequency map for the first complete window.
for (int i = 0; i < k; i++) {
frequency[nums[i]]++;
}
// Each map entry represents one distinct value in the window.
result.push_back(frequency.size());
for (int right = k; right < nums.size(); right++) {
int outgoing = nums[right - k];
// Remove only one occurrence of the outgoing value.
frequency[outgoing]--;
if (frequency[outgoing] == 0) {
frequency.erase(outgoing);
}
// Include the incoming value in the current window.
int incoming = nums[right];
frequency[incoming]++;
// Record the count after both window updates are complete.
result.push_back(frequency.size());
}
return result;
}
};
// Driver code
int main() {
vector<int> nums = {4, 4, 2, 5, 2, 6};
int k = 3;
// Create an instance of class Solution.
Solution sol;
vector<int> result = sol.distinctNumbers(nums, k);
// Print the returned counts in array format.
cout << "[";
for (int i = 0; i < result.size(); i++) {
if (i > 0) cout << ", ";
cout << result[i];
}
cout << "]\n";
return 0;
}

Complexity Analysis

Time Complexity: O(N) expected time. Building the first window takes O(K) time, and each subsequent move performs a constant number of hash-map operations.

Space Complexity: O(K) auxiliary space because the frequency map contains at most K distinct values. The returned array uses an additional O(N - K) space.

Interview follow-up Questions

Removing one occurrence and adding another restores that value’s original frequency, so the distinct count remains unchanged. The count is recorded after both updates, even if the value’s entry is temporarily removed and added again.

ArraysSliding WindowTCS NQT

Read Similar Blogs

Comments0