Distinct elements in
every window

Count the distinct values in each sliding window

Given an array and a window size B, slide a window of that width across the array and report how many distinct values sit inside each position. For A = [1,2,1,3,4,3] with B = 3:

Answer: [2, 3, 3, 2].

"Every window of size B" means sliding window

Phrases like fixed-size subarray, window of size K, or every consecutive K elements are the tell. The reason is overlap: consecutive windows share B − 1 elements. Going from [1,2,1] to [2,1,3], only two things happen — 1 leaves the left, 3 enters the right. Everything in between is untouched.

You need counts, not just membership

A HashSet is tempting, but it breaks the moment duplicates leave. Take window [1,2,1] — the set is {1, 2}. When the leftmost 1 slides out, the window becomes [2,1], which still contains a 1. If you'd done set.remove(1) you'd have wrongly dropped it.

Step the window across the array

Pick an example and slide the window one position at a time. The incoming element lifts in from the right, the outgoing one drops out from the left, and the frequency map on the right updates live. Bars show each value's count; the distinct total is just the number of bars.

Build once, then swap one in and one out

Build the frequency map for the first window (indices 0…B−1). After that, for each new position i from B to N−1: the entering element is A[i] and the leaving element is A[i − B].

The sample, window by window

For [1,2,1,3,4,3], B = 3. Watch the map stay exactly in sync with the current window:

Clean Java with a HashMap

import java.util.*;

static int[] countDistinct(int n, int b, int[] arr) {
    if (b > n) return new int[0];      // window bigger than array

    int[] result = new int[n - b + 1];
    Map<Integer,Integer> freq = new HashMap<>();

    // build the first window
    for (int i = 0; i < b; i++)
        freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1);
    result[0] = freq.size();

    int r = 1;
    for (int i = b; i < n; i++) {
        int out = arr[i - b];               // leaving from the left
        freq.put(out, freq.get(out) - 1);
        if (freq.get(out) == 0) freq.remove(out);  // keep size == distinct

        int in = arr[i];                    // entering from the right
        freq.put(in, freq.getOrDefault(in, 0) + 1);

        result[r++] = freq.size();
    }
    return result;
}

Building the first window is O(B); every slide after is one decrement and one increment, each O(1) on average. Total: O(N) time, O(B) space — you can't beat O(N) since you must read every element at least once.

Four ways this breaks

When values are bounded, skip the hashing

If the constraint says values fit a small fixed range (e.g. 1 ≤ Aᵢ ≤ 10000), swap the map for a plain integer array and keep a manual distinctCount. Same logic, no hashing overhead.

The decision rule: small bounded domain → array; large or unbounded → HashMap. Learn the map version first — it carries over to problems where you can't predict the value range.

Sliding window is really incremental state

The strongest mental model isn't "move two pointers." It's: keep a piece of state describing the current window, then transition it by subtracting the outgoing element and adding the incoming one. The answer is derived from that state. Only the state changes from problem to problem:

Reconstruct it, don't memorize it

1. The question is about every fixed-size contiguous window.
2. Adjacent windows overlap heavily — only one leaves, one enters.
3. So update incrementally instead of recomputing.
4. A set can't handle duplicates leaving, so track frequencies.
5. On each slide: decrement outgoing (drop at zero), increment incoming.
6. Distinct count = number of live keys in the map.