.png)
Count Distinct Elements in Every Window
Problem Statement
You are given an integer array arr of size n and an integer k.
For every contiguous subarray (window) of size k, return the count of distinct elements present in that window.
Example
Input
arr = [1, 2, 1, 3, 4, 2, 3]
k = 4
Output
[3, 4, 4, 3]
Why This Problem Is Important
Sliding window fundamentals
Hashing and frequency management
Very common interview question
Tests optimization from brute force to optimal
Foundation for window-based problems
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force + Set | O(n × k) | O(k) |
| Approach 2 | Sliding Window + Hash Map | O(n) | O(k) |
| Approach 3 | Sliding Window + Ordered Map | O(n log k) | O(k) |
Approach 1: Brute Force
Idea
For every window of size k:
- Use a set to store elements
- Count unique elements
Algorithm
- Loop from i = 0 to n - k
- Create empty set
- Insert k elements into the set
- Store set size
Time & Space Complexity
Time: O(n × k)
Space: O(k)
C
#include
int main() {
int arr[] = {1,2,1,3,4,2,3};
int n = 7, k = 4;
for(int i = 0; i <= n - k; i++) {
int count = 0;
for(int j = i; j < i + k; j++) {
int found = 0;
for(int x = i; x < j; x++) {
if(arr[x] == arr[j]) {
found = 1;
break;
}
}
if(!found) count++;
}
printf("%d ", count);
}
return 0;
}
Output
3 4 4 3
C++
#include
#include
using namespace std;
int main() {
int arr[] = {1,2,1,3,4,2,3};
int n = 7, k = 4;
for(int i = 0; i <= n - k; i++) {
unordered_set s;
for(int j = i; j < i + k; j++)
s.insert(arr[j]);
cout << s.size() << " ";
}
return 0;
}
Output
3 4 4 3
Java
import java.util.HashSet;
public class Main {
public static void main(String[] args) {
int[] arr = {1,2,1,3,4,2,3};
int k = 4;
for(int i = 0; i <= arr.length - k; i++) {
HashSet set = new HashSet<>();
for(int j = i; j < i + k; j++)
set.add(arr[j]);
System.out.print(set.size() + " ");
}
}
}
Output
3 4 4 3
Python
arr = [1,2,1,3,4,2,3]
k = 4
for i in range(len(arr) - k + 1):
print(len(set(arr[i:i+k])), end=" ")
Output
3 4 4 3
JavaScript
let arr = [1,2,1,3,4,2,3];
let k = 4;
for(let i = 0; i <= arr.length - k; i++) {
let s = new Set();
for(let j = i; j < i + k; j++)
s.add(arr[j]);
console.log(s.size);
}
Output
3
4
4
3
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {1,2,1,3,4,2,3};
int k = 4;
for(int i = 0; i <= arr.Length - k; i++) {
HashSet set = new HashSet();
for(int j = i; j < i + k; j++)
set.Add(arr[j]);
Console.Write(set.Count + " ");
}
}
}
Output
3 4 4 3
Approach 2: Sliding Window + Hash Map (Optimal)
Idea
Maintain frequency map for current window:
- Add incoming element
- Remove outgoing element
- Map size = distinct count
Algorithm
- Create frequency map
- Fill first window
- Slide window:
- Add new element
- Decrease count of outgoing element
- Remove if frequency becomes zero
Time & Space Complexity
Time: O(n)
Space: O(k)}
C++
#include
#include
using namespace std;
int main() {
int arr[] = {1,2,1,3,4,2,3};
int n = 7, k = 4;
unordered_map freq;
// first window
for(int i = 0; i < k; i++)
freq[arr[i]]++;
cout << freq.size() << " ";
// slide window
for(int i = k; i < n; i++) {
freq[arr[i]]++;
freq[arr[i-k]]--;
if(freq[arr[i-k]] == 0)
freq.erase(arr[i-k]);
cout << freq.size() << " ";
}
return 0;
}
Java
import java.util.HashMap;
public class Main {
public static void main(String[] args) {
int[] arr = {1,2,1,3,4,2,3};
int k = 4;
HashMap map = new HashMap<>();
for(int i = 0; i < k; i++)
map.put(arr[i], map.getOrDefault(arr[i],0) + 1);
System.out.print(map.size() + " ");
for(int i = k; i < arr.length; i++) {
map.put(arr[i], map.getOrDefault(arr[i],0) + 1);
map.put(arr[i-k], map.get(arr[i-k]) - 1);
if(map.get(arr[i-k]) == 0)
map.remove(arr[i-k]);
System.out.print(map.size() + " ");
}
}
}
Python
from collections import defaultdict
arr = [1,2,1,3,4,2,3]
k = 4
freq = defaultdict(int)
for i in range(k):
freq[arr[i]] += 1
print(len(freq), end=" ")
for i in range(k, len(arr)):
freq[arr[i]] += 1
freq[arr[i-k]] -= 1
if freq[arr[i-k]] == 0:
del freq[arr[i-k]]
print(len(freq), end=" ")
JavaScript
let arr = [1,2,1,3,4,2,3];
let k = 4;
let freq = {};
for(let i = 0; i < k; i++)
freq[arr[i]] = (freq[arr[i]] || 0) + 1;
process.stdout.write(Object.keys(freq).length + " ");
for(let i = k; i < arr.length; i++) {
freq[arr[i]] = (freq[arr[i]] || 0) + 1;
freq[arr[i-k]]--;
if(freq[arr[i-k]] === 0)
delete freq[arr[i-k]];
process.stdout.write(Object.keys(freq).length + " ");
}
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {1,2,1,3,4,2,3};
int k = 4;
Dictionary freq = new Dictionary();
for(int i = 0; i < k; i++) {
if(!freq.ContainsKey(arr[i]))
freq[arr[i]] = 0;
freq[arr[i]]++;
}
Console.Write(freq.Count + " ");
for(int i = k; i < arr.Length; i++) {
if(!freq.ContainsKey(arr[i]))
freq[arr[i]] = 0;
freq[arr[i]]++;
freq[arr[i-k]]--;
if(freq[arr[i-k]] == 0)
freq.Remove(arr[i-k]);
Console.Write(freq.Count + " ");
}
}
}Output:
3 4 4 3Approach 3: Sliding Window + Ordered Map
Same logic as Approach 2 but maintains sorted order.
Complexity
Time: O(n log k)
Space: O(k)
C++
#include
#include
using namespace std;
int main() {
int arr[] = {1,2,1,3,4,2,3};
int n = 7, k = 4;
map mp;
for(int i = 0; i < k; i++)
mp[arr[i]]++;
cout << mp.size() << " ";
for(int i = k; i < n; i++) {
mp[arr[i]]++;
mp[arr[i-k]]--;
if(mp[arr[i-k]] == 0)
mp.erase(arr[i-k]);
cout << mp.size() << " ";
}
return 0;
}
Java
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
int[] arr = {1,2,1,3,4,2,3};
int k = 4;
TreeMap map = new TreeMap<>();
for(int i = 0; i < k; i++)
map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
System.out.print(map.size() + " ");
for(int i = k; i < arr.length; i++) {
map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
map.put(arr[i-k], map.get(arr[i-k]) - 1);
if(map.get(arr[i-k]) == 0)
map.remove(arr[i-k]);
System.out.print(map.size() + " ");
}
}
}
Python
from collections import defaultdict
arr = [1,2,1,3,4,2,3]
k = 4
freq = defaultdict(int)
for i in range(k):
freq[arr[i]] += 1
print(len(freq), end=" ")
for i in range(k, len(arr)):
freq[arr[i]] += 1
freq[arr[i-k]] -= 1
if freq[arr[i-k]] == 0:
del freq[arr[i-k]]
print(len(freq), end=" ")
JavaScript
let arr = [1,2,1,3,4,2,3];
let k = 4;
let map = new Map();
for(let i = 0; i < k; i++)
map.set(arr[i], (map.get(arr[i]) || 0) + 1);
process.stdout.write(map.size + " ");
for(let i = k; i < arr.length; i++) {
map.set(arr[i], (map.get(arr[i]) || 0) + 1);
map.set(arr[i-k], map.get(arr[i-k]) - 1);
if(map.get(arr[i-k]) === 0)
map.delete(arr[i-k]);
process.stdout.write(map.size + " ");
}
C#
using System;
using System.Collections.Generic;
class Program {
static void Main() {
int[] arr = {1,2,1,3,4,2,3};
int k = 4;
SortedDictionary map = new SortedDictionary();
for(int i = 0; i < k; i++) {
if(!map.ContainsKey(arr[i]))
map[arr[i]] = 0;
map[arr[i]]++;
}
Console.Write(map.Count + " ");
for(int i = k; i < arr.Length; i++) {
if(!map.ContainsKey(arr[i]))
map[arr[i]] = 0;
map[arr[i]]++;
map[arr[i-k]]--;
if(map[arr[i-k]] == 0)
map.Remove(arr[i-k]);
Console.Write(map.Count + " ");
}
}
}Output:
3 4 4 3
Summary
Brute force is easy but slow
Sliding window with HashMap is optimal and interview-preferred
Ordered map is used only when sorted output is required
Next Problem in the Series
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
