Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Keep a frequency map for the k elements currently in the window.
  2. 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