Log inSign up
mediumGeeksforGeeksNot Started

Count Distinct Elements in Every Window

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an integer array arr[] of size n and an integer k, return the count of distinct elements in all contiguous sliding windows of size k.

Return an array/list of integers where the i-th integer represents the number of distinct elements in the window from index i to i + k - 1.

Example 1 · Standard Array:

Input: arr = [1, 2, 1, 3, 4, 2, 3], k = 4
Output: [3, 4, 4, 3]
Explanation: Window 1: [1, 2, 1, 3] -> 3 distinct elements (1, 2, 3) Window 2: [2, 1, 3, 4] -> 4 distinct elements (1, 2, 3, 4) Window 3: [1, 3, 4, 2] -> 4 distinct elements (1, 2, 3, 4) Window 4: [3, 4, 2, 3] -> 3 distinct elements (2, 3, 4)

Example 2 · All Identical Elements:

Input: arr = [4, 4, 4, 4], k = 2
Output: [1, 1, 1]
Explanation: Every window of size 2 contains only [4, 4], so distinct count is always 1.

Constraints:

  • 1 <= k <= arr.length <= 105
  • 1 <= arr[i] <= 104

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Sliding Window technique with fixed window size
  • Hash Map / Dictionary operations (insert, lookup, delete)

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the fixed-size sliding window state transition.
  • Understand why removing 0-frequency keys is essential for map size queries.
  • Compare direct frequency indexing vs hash map dynamic sizing.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Fixed window size k moving across an array.
  • Requires tracking frequencies or distinct elements inside the current window.
  • Adjacent windows overlap heavily (sharing k-1 elements).

Algorithmic Decision Tree:

  • Use a fixed-size sliding window with a frequency map countMap.
  • When an outgoing element frequency drops to 0, erase the key completely so map.size() reflects distinct elements.

Connected Patterns:

Sliding Window MaximumSubarray Sum Equals KLongest Substring Without Repeating Characters

1. Brute Force — Hash Set per Window

Intuition

For each window of size k, construct a fresh hash set, insert all k elements, and record the number of unique elements.

Algorithm

  1. Initialize required state variables and allocate data structures for Brute Force — Hash Set per Window.
  2. Iterate through the input array and apply the core algorithmic condition.
  3. Update boundaries, frequencies, or pointers in accordance with the invariant.
  4. Return the computed result or transformed array.

Brute Force — Hash Set per Window Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 1, 3, 4, 2]
Current operationSTEP 1 OF 6
Phase 1 — Window Initialization: Both left and right pointers anchor at index 0
Visual state
Values and pointers at this exact step
pointers
S
1
2
1
3
4
2
0
↑ L↑ R
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Window Value
1
Window Length
1
Best Metric
Evaluating...
Check / comparison
Current element arr[0]=1. Window span [0..0].
Decision / next transition
Initialize window state and evaluate target constraint.
Why this step matters

Phase 1 — Window Initialization: Both left and right pointers anchor at index 0. Initial window length is 1 with sum/metric=1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<int> countDistinct(vector<int>& arr, int k) {
10 int n = arr.size();
11 vector<int> result;
12
13 for (int i = 0; i <= n - k; i++) {
14 unordered_set<int> uniqueElements;
15 for (int j = i; j < i + k; j++) {
16 uniqueElements.insert(arr[j]);
17 }
18 result.push_back(uniqueElements.size());
19 }
20
21 return result;
22 }
23};
24
25int main() {
26 Solution sol;
27 vector<int> arr = {1, 2, 1, 3, 4, 2, 3};
28 int k = 4;
29 cout << "Input: arr = [1, 2, 1, 3, 4, 2, 3], k = 4\n";
30 vector<int> res = sol.countDistinct(arr, k);
31 cout << "Brute Force Result: [";
32 for (size_t i = 0; i < res.size(); i++) {
33 cout << res[i] << (i + 1 < res.size() ? ", " : "");
34 }
35 cout << "]\n";
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force — Hash Set per Window.
  • Space complexity: O(1) — Space complexity for Brute Force — Hash Set per Window.

Why Brute Force Doesn't Scale:

For N = 100,000 and K = 50,000, N * K = 5 * 109 operations, which takes several seconds.

Sliding window does 2 operations per window, reducing 5 billion operations to ~200,000 operations (25,000x speedup).

2. Better — Frequency Array with Distinct Counter

Intuition

When element values are bounded (e.g. <= 104), maintain a flat frequency array. Keep a running distinctCount variable that increments when frequency goes 0 -> 1 and decrements when frequency goes 1 -> 0.

Algorithm

  1. When element values are bounded (e.g
  2. <= 104), maintain a flat frequency array
  3. Keep a running distinctCount variable that increments when frequency goes 0 -> 1 and decrements when frequency goes 1 -> 0.

Better — Frequency Array with Distinct Counter Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 1, 3, 4, 2]
Current operationSTEP 1 OF 6
Phase 1 — Window Initialization: Both left and right pointers anchor at index 0
Visual state
Values and pointers at this exact step
pointers
S
1
2
1
3
4
2
0
↑ L↑ R
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Window Value
1
Window Length
1
Best Metric
Evaluating...
Check / comparison
Current element arr[0]=1. Window span [0..0].
Decision / next transition
Initialize window state and evaluate target constraint.
Why this step matters

Phase 1 — Window Initialization: Both left and right pointers anchor at index 0. Initial window length is 1 with sum/metric=1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<int> countDistinct(vector<int>& arr, int k) {
10 int n = arr.size();
11 int maxVal = 0;
12 for (int x : arr) maxVal = max(maxVal, x);
13
14 vector<int> freq(maxVal + 1, 0);
15 vector<int> result;
16 int distinctCount = 0;
17
18 // Initialize first window
19 for (int i = 0; i < k; i++) {
20 if (freq[arr[i]] == 0) distinctCount++;
21 freq[arr[i]]++;
22 }
23 result.push_back(distinctCount);
24
25 // Slide the window
26 for (int i = k; i < n; i++) {
27 // Remove outgoing element arr[i - k]
28 freq[arr[i - k]]--;
29 if (freq[arr[i - k]] == 0) distinctCount--;
30
31 // Add incoming element arr[i]
32 if (freq[arr[i]] == 0) distinctCount++;
33 freq[arr[i]]++;
34
35 result.push_back(distinctCount);
36 }
37
38 return result;
39 }
40};
41
42int main() {
43 Solution sol;
44 vector<int> arr = {1, 2, 1, 3, 4, 2, 3};
45 int k = 4;
46 cout << "Input: arr = [1, 2, 1, 3, 4, 2, 3], k = 4\n";
47 vector<int> res = sol.countDistinct(arr, k);
48 cout << "Better (Frequency Array) Result: [";
49 for (size_t i = 0; i < res.size(); i++) {
50 cout << res[i] << (i + 1 < res.size() ? ", " : "");
51 }
52 cout << "]\n";
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better — Frequency Array with Distinct Counter.
  • Space complexity: O(N) — Space complexity for Better — Frequency Array with Distinct Counter.

3. Optimal — Sliding Window + Frequency Hash Map

Intuition

Maintain a hash map of frequencies for the k elements currently in the window. As the window slides: decrement the count of arr[i - k] (and erase the key if count drops to 0), then increment the count of arr[i]. The hash map size directly yields the distinct count in O(1) time.

Algorithm

  1. Maintain a hash map of frequencies for the k elements currently in the window
  2. As the window slides: decrement the count of arr[i - k] (and erase the key if count drops to 0), then increment the count of arr[i]
  3. The hash map size directly yields the distinct count in O(1) time.

Optimal — Sliding Window + Frequency Hash Map Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 1, 3, 4, 2]
Current operationSTEP 1 OF 6
Phase 1 — Window Initialization: Both left and right pointers anchor at index 0
Visual state
Values and pointers at this exact step
pointers
S
1
2
1
3
4
2
0
↑ L↑ R
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Window Value
1
Window Length
1
Best Metric
Evaluating...
Check / comparison
Current element arr[0]=1. Window span [0..0].
Decision / next transition
Initialize window state and evaluate target constraint.
Why this step matters

Phase 1 — Window Initialization: Both left and right pointers anchor at index 0. Initial window length is 1 with sum/metric=1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5using namespace std;
6
7class Solution {
8public:
9 vector<int> countDistinct(vector<int>& arr, int k) {
10 int n = arr.size();
11 unordered_map<int, int> freqMap;
12 vector<int> result;
13
14 // Populate initial window of size k
15 for (int i = 0; i < k; i++) {
16 freqMap[arr[i]]++;
17 }
18 result.push_back(freqMap.size());
19
20 // Slide window from k to n - 1
21 for (int i = k; i < n; i++) {
22 int outgoing = arr[i - k];
23 int incoming = arr[i];
24
25 // Remove outgoing
26 freqMap[outgoing]--;
27 if (freqMap[outgoing] == 0) {
28 freqMap.erase(outgoing);
29 }
30
31 // Add incoming
32 freqMap[incoming]++;
33
34 result.push_back(freqMap.size());
35 }
36
37 return result;
38 }
39};
40
41int main() {
42 Solution sol;
43 vector<int> arr = {1, 2, 1, 3, 4, 2, 3};
44 int k = 4;
45 cout << "Input: arr = [1, 2, 1, 3, 4, 2, 3], k = 4\n";
46 vector<int> res = sol.countDistinct(arr, k);
47 cout << "Optimal Result: [";
48 for (size_t i = 0; i < res.size(); i++) {
49 cout << res[i] << (i + 1 < res.size() ? ", " : "");
50 }
51 cout << "]\n";
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal — Sliding Window + Frequency Hash Map.
  • Space complexity: O(1) — Space complexity for Optimal — Sliding Window + Frequency Hash Map.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash Set per WindowO(N * K)O(K)For each starting index i from 0 to n - k, iterate through the window of size k, insert all elements into a Set, and append set.size to the answer.Rebuilding the hash set from scratch on every step.
2.Better — Frequency Array (Direct Addressing)O(N)O(MAX_VAL)Use a fixed direct frequency array when arr[i] <= 104. Increment distinctCounter when frequency transitions 0 -> 1, decrement when 1 -> 0.Memory dependent on maximum element value.
3.Optimal — Sliding Window + Frequency Hash MapOptimalO(N)O(K)Maintain a frequency hash map for the current window. Slide the window: decrement outgoing element (remove if 0) and increment incoming element. Map size is the distinct count.None; optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Count Distinct Elements in Every Window?

2.Why is the brute force approach suboptimal for large inputs in Count Distinct Elements in Every Window?

3.Which data structure or technique enables the optimal solution for Count Distinct Elements in Every Window?

Back to DSA Sheet