Practice › Sliding Window
Distinct Elements in Every Window
Medium · Sliding Window · Asked at Amazon, Microsoft, Flipkart
For every window of size k, print the number of distinct elements in it.
Input
First line: n. Second line: n integers. Third line: k.
Output
n − k + 1 numbers, space-separated.
Constraints
- 1 ≤ k ≤ n ≤ 10^5
Keep a frequency hash map of the current window.
Example 1
Input
7 1 2 1 3 4 2 3 4
Output
3 4 4 3
Example 2
Input
3 4 4 4 2
Output
1 1
Hints
- Keep a frequency map for the k elements currently in the window.
- When an element leaves, decrease its count and remove it from the map when the count hits 0. The map's size is the answer.
Approach
Fill the map with the first k elements. Then slide: add a[i], decrease the count of a[i − k] and delete that key once its count is 0. After each window, the number of keys in the map is its distinct count. Each step is O(1) on average.
Complexity: O(n) average time · O(k) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
cin >> k;
unordered_map<long long, int> freq;
for (int i = 0; i < n; i++) {
freq[a[i]]++;
if (i >= k && --freq[a[i - k]] == 0) freq.erase(a[i - k]);
if (i >= k - 1) cout << freq.size() << (i + 1 < n ? " " : "\n");
}
return 0;
}Python solution
import sys
from collections import defaultdict
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, k = data[1 : n + 1], data[n + 1]
freq = defaultdict(int)
out = []
for i, x in enumerate(a):
freq[x] += 1
if i >= k:
old = a[i - k]
freq[old] -= 1
if freq[old] == 0:
del freq[old]
if i >= k - 1:
out.append(len(freq))
print(*out)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
int k = sc.nextInt();
Map<Long, Integer> freq = new HashMap<>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
freq.merge(a[i], 1, Integer::sum);
if (i >= k && freq.merge(a[i - k], -1, Integer::sum) == 0) freq.remove(a[i - k]);
if (i >= k - 1) sb.append(sb.length() > 0 ? " " : "").append(freq.size());
}
System.out.println(sb);
}
}Solve Distinct Elements in Every Window online · All practice problems