Count distinct values in every sliding window

Question: Count distinct values in every sliding window

Companies: Google, Microsoft, Meta

Difficulty: Easy

Problem statement

Given an integer array nums and a window size k, return a list with one entry per contiguous window of length k (there are len(nums) - k + 1 of them). Each entry is the number of different values inside that window.

Implement:

def count_distinct_in_windows(nums: list[int], k: int) -> list[int]: ...

Constraints

• 1 <= k <= len(nums) <= 10^5
• Values can be any integers: negative, zero, or positive.
• Aim for better than O(n * k) time.

Example 1

nums = [4, 4, 7, 2, 7, 4, 9], k = 3
output: [2, 3, 2, 3, 3]

The windows are [4,4,7], [4,7,2], [7,2,7], [2,7,4], [7,4,9].

Example 2

nums = [-1, 0, -1, 0, 1], k = 2
output: [2, 2, 2, 2]

Approach

We need one number per window of size k: how many different values that
window holds. There are n - k + 1 windows.

Brute force, O(n * k). For each start i, build set(nums[i:i+k]) and
take its size. It is correct and a good oracle, but it rebuilds the set from
scratch even though neighbouring windows share k - 1 elements.

Optimal: sliding window with a frequency map, O(n). Keep a dictionary
count[value] -> occurrences inside the current window and an integer
distinct equal to the number of keys with a positive count.

1. Fill the map with the first k elements.
2. Record distinct for the first window.
3. For each new index right from k to n - 1:
   • Remove nums[right - k]: decrement its count; if it reaches 0, delete
     the key and decrement distinct.
   • Add nums[right]: if its count was 0, increment distinct; then
     increment the count.
   • Record distinct.

Each step touches exactly two values, so the cost per window is O(1)
expected (hash map operations).

Order of remove and add does not matter for correctness as long as both
happen before recording, but removing first keeps the map at most k keys.
Deleting zero-count keys means len(count) equals distinct, so you can
drop the separate counter if you prefer; keeping it makes the invariant
explicit.

Invariant: before recording window [right - k + 1, right], count holds
exactly the multiset of that window, every stored count is positive, and
distinct == len(count).

Code

from collections import defaultdict
from typing import Dict, List


def count_distinct_in_windows(nums: List[int], k: int) -> List[int]:
    """Return the number of distinct values in every window of size k."""
    n = len(nums)
    if k <= 0 or k > n:
        raise ValueError("k must satisfy 1 <= k <= len(nums)")

    count: Dict[int, int] = defaultdict(int)
    distinct = 0

    def add(x: int) -> None:
        nonlocal distinct
        if count[x] == 0:
            distinct += 1
        count[x] += 1

    def remove(x: int) -> None:
        nonlocal distinct
        count[x] -= 1
        if count[x] == 0:
            del count[x]
            distinct -= 1

    for i in range(k):
        add(nums[i])
    result = [distinct]

    for right in range(k, n):
        remove(nums[right - k])
        add(nums[right])
        result.append(distinct)
    return result


def brute_force(nums: List[int], k: int) -> List[int]:
    """O(n * k) oracle."""
    return [len(set(nums[i:i + k])) for i in range(len(nums) - k + 1)]


if __name__ == "__main__":
    import random

    assert count_distinct_in_windows([4, 4, 7, 2, 7, 4, 9], 3) == [2, 3, 2, 3, 3]
    assert count_distinct_in_windows([5], 1) == [1]
    assert count_distinct_in_windows([3, 3, 3, 3], 2) == [1, 1, 1]
    assert count_distinct_in_windows([1, 2, 3, 4], 4) == [4]
    assert count_distinct_in_windows([-1, 0, -1, 0, 1], 2) == [2, 2, 2, 2]
    assert count_distinct_in_windows([1, 2, 1, 3], 1) == [1, 1, 1, 1]
    for _ in range(500):
        n = random.randint(1, 30)
        arr = [random.randint(-4, 4) for _ in range(n)]
        k = random.randint(1, n)
        assert count_distinct_in_windows(arr, k) == brute_force(arr, k)
    print("ok")

Complexity

• Time: O(n) expected. The first window costs O(k); each of the remaining
  n - k windows costs one remove and one add, both O(1) expected.
• Space: O(k) for the frequency map (at most k keys), plus O(n - k + 1)
  for the output.
• Brute force: O(n * k) time, O(k) extra space.

Test cases

• nums = [4, 4, 7, 2, 7, 4, 9], k = 3 -> [2, 3, 2, 3, 3]
• nums = [5], k = 1 -> [1] (single element)
• nums = [3, 3, 3, 3], k = 2 -> [1, 1, 1] (all equal)
• nums = [1, 2, 3, 4], k = 4 -> [4] (window is the whole array)
• nums = [-1, 0, -1, 0, 1], k = 2 -> [2, 2, 2, 2] (negatives and zero)
• nums = [1, 2, 1, 3], k = 1 -> [1, 1, 1, 1] (every window has one value)
• nums = [1, 2, 3], k = 0 or k = 4 -> ValueError (outside the stated
  constraints; say how you would handle it)
• Randomised check against the brute force for small arrays.

Follow-ups

• Values are small non-negative integers (e.g. 0 <= x < 10^5). Replace
  the dict with a fixed-size array of counts. Same logic, worst-case O(1) per
  step instead of expected, and better cache behaviour.
• Streaming input, answer after each arrival. Keep a deque of the last
  k values next to the map. On each new value, push it, pop the oldest when
  the deque exceeds k, and update the map. Memory stays O(k) no matter how
  long the stream is.
• Arbitrary range queries "distinct count in nums[l..r]". The sliding
  trick no longer applies. Offline: sort queries by r, sweep right, keep a
  Fenwick tree with a 1 at the last occurrence of each value, and answer with
  a prefix sum, O((n + q) log n). Mo's algorithm is an alternative at
  O((n + q) sqrt n). Online: a persistent segment tree.
• Return the windows with exactly / at most d distinct values, or the
  longest subarray with at most d distinct. For a variable-size window,
  grow the right end and shrink the left while distinct > d; the same
  add/remove helpers work unchanged.
• Huge k and a memory budget (stream analytics). Exact counting needs
  O(k) memory. Approximate with HyperLogLog per time bucket, or a sliding
  HyperLogLog, and discuss the error bounds.

Interviewer expectations

Mid-level (L4)

• States the brute force and its O(n * k) cost, then moves to the sliding
  window without prompting.
• Writes correct code that deletes or ignores zero-count keys, so the
  distinct count is right after an element leaves.
• Tests duplicates, k = 1, and k = n.

Senior (L5)

• States the invariant and explains why the update is O(1) per window.
• Points out the expected versus worst-case hash cost and offers the
  counting array when the value range is bounded.
• Handles the streaming version with a deque and bounded memory.

Staff (L6+)

• Moves quickly to the general range-query problem and explains the offline
  Fenwick-tree sweep or Mo's algorithm, with their trade-offs.
• Discusses approximate distinct counting (HyperLogLog) for very large
  windows or distributed streams, and when exact answers are worth the memory.
• Frames API choices: input validation, returning a generator for long
  inputs, and how the helper functions generalise to variable-size windows.