Frequency Counting Process

Frequency counting emphasizes the process: streaming updates, decrements when a window slides, and keeping auxiliary facts (unique count, odd character) in sync.

Why this shows up in the real world

Real-time fraud tracks card usage per minute; game servers tally actions per session with decay.

Core idea (explained for students)

On window shift: decrement outgoing key, remove key if zero, increment incoming. Maintain unique = sum(1 for c in freq.values() if c) in O(1) amortized with careful updates.

Try this in Python

from collections import defaultdict


def distinct_in_windows(nums: list[int], k: int) -> list[int]:
    freq: dict[int, int] = defaultdict(int)
    out = []
    for i, x in enumerate(nums):
        freq[x] += 1
        if i >= k:
            y = nums[i - k]
            freq[y] -= 1
            if freq[y] == 0:
                del freq[y]
        if i >= k - 1:
            out.append(len(freq))
    return out


print(distinct_in_windows([1, 2, 2, 3], 2))

Common mistakes

• Decrementing below zero—assert or guard.
• Off-by-one window bounds inclusive vs exclusive.

Key takeaways

• Template: defaultdict(int) + while r < n: expand, while invalid: shrink.
• Log intermediate frequencies when debugging.