Sliding Window Distinct Count

Description

"How many distinct values are in each window of k elements?" Recounting every window from scratch costs O(k) per window. Moving the window one step changes only two things: one value comes in on the right and one leaves on the left. So the answer can be updated instead of recomputed, by keeping a count per value and removing values whose count drops to zero. The same bookkeeping, with the "at most k" trick, counts subarrays with exactly k distinct values.

We'll go from simple to more technical:

1. The pattern: a fixed window with a frequency map, updated as values enter and leave.
2. A second flavor: exactly k = at most k minus at most k - 1.
3. Where distinct counting shows up in production (unique visitors, active users).
4. What breaks it: zero-count keys, recounting, counting "exactly" directly, int counts.

The approach

int[] distinctCountInWindows(int[] nums, int k) {
    int[] result = new int[nums.length - k + 1];
    Map<Integer, Integer> freq = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        freq.merge(nums[i], 1, Integer::sum);                           // value enters on the right
        if (i >= k && freq.merge(nums[i - k], -1, Integer::sum) == 0) {
            freq.remove(nums[i - k]);                                   // value fully left: drop the key
        }
        if (i >= k - 1) result[i - k + 1] = freq.size();                // size = distinct values now
    }
    return result;
}

def distinct_count_in_windows(nums: list[int], k: int) -> list[int]:
    result = []
    freq = {}
    for i, x in enumerate(nums):
        freq[x] = freq.get(x, 0) + 1                   # value enters on the right
        if i >= k:
            out = nums[i - k]
            freq[out] -= 1
            if freq[out] == 0:
                del freq[out]                          # value fully left: drop the key
        if i >= k - 1:
            result.append(len(freq))                   # size = distinct values now
    return result

The map holds exactly the values inside the window with their counts, so its size is the answer. That only works if a key is removed the moment its count reaches 0; a zero-count key left behind still counts toward size(). In Python, a Counter is the easy way to get this wrong: c[x] -= 1 leaves a key at 0 and len(c) still counts it, so del the key explicitly. Every value enters and leaves once, so the whole scan is O(n) with O(k) space. When values are small integers (here at most 10^5), a count array and a counter that goes up when a count becomes 1 and down when it becomes 0 do the same job without hashing.

A second flavor: exactly k = at most k minus at most k - 1

"How many subarrays contain exactly k distinct values?" A single shrinking window doesn't work: for one right end, several different starts can have exactly k distinct values. On [1, 2, 1, 2, 3] with k = 2 the answer is 7, and a single window that counts one subarray per right end finds only 4. "At most k" is easy to count, though, and exactly k is a difference of two of them:

long subarraysWithKDistinct(int[] nums, int k) {
    return atMost(nums, k) - atMost(nums, k - 1);
}

long atMost(int[] nums, int k) {                        // subarrays with at most k distinct values
    Map<Integer, Integer> freq = new HashMap<>();
    long count = 0;
    for (int left = 0, right = 0; right < nums.length; right++) {
        freq.merge(nums[right], 1, Integer::sum);
        while (freq.size() > k) {                       // too many distinct: shrink from the left
            if (freq.merge(nums[left], -1, Integer::sum) == 0) freq.remove(nums[left]);
            left++;
        }
        count += right - left + 1;                      // every start from left to right is valid
    }
    return count;
}

def subarrays_with_k_distinct(nums: list[int], k: int) -> int:
    return at_most(nums, k) - at_most(nums, k - 1)


def at_most(nums: list[int], k: int) -> int:           # subarrays with at most k distinct values
    freq = {}
    count = left = 0
    for right, x in enumerate(nums):
        freq[x] = freq.get(x, 0) + 1
        while len(freq) > k:                           # too many distinct: shrink from the left
            freq[nums[left]] -= 1
            if freq[nums[left]] == 0:
                del freq[nums[left]]
            left += 1
        count += right - left + 1                      # every start from left to right is valid
    return count

For each right end, the shortest valid window starts at left, and every longer window that still ends at right and starts after left has at most k distinct values too - right - left + 1 of them. The count can reach n(n + 1)/2, about 5 * 10^9 for n = 10^5, so it's a long.

Where you'll see it

"Distinct users active in the last five minutes" and "distinct IPs hitting this endpoint" are rolling distinct counts. At large scale they're estimated rather than counted exactly: Redis's HyperLogLog (PFADD/PFCOUNT) estimates a distinct count with 0.81% standard error in at most 12 KB, however many values it sees.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why must a key be removed when its count reaches 0?

2. Why does exactly(k) equal atMost(k) - atMost(k - 1)?

3. In atMost, why does each right end add right - left + 1?

Key takeaways

• Slide the window: add the incoming count, subtract the outgoing one, delete keys that reach 0.
• The map's size is the window's distinct count - O(n) overall.
• "Exactly k" = atMost(k) - atMost(k - 1); count right - left + 1 per right end.
• Subarray counts need a long.
• At scale, distinct counts are estimated (HyperLogLog).