Frequency Array

A frequency array stores counts in a dense vector indexed by key—ideal when keys are integers in a known range (ASCII, grades, small IDs) instead of a sparse dict.

Why this shows up in the real world

Competitive programming uses count arrays for O(1) increment; embedded systems prefer fixed-size tables over dynamic allocation.

Core idea (explained for students)

Map key → index (ord(c)-ord('a')), maintain cnt[i], answer queries like “how many of this letter?” in O(1). Remember to reset or slice-copy when reusing buffers.

Try this in Python

def freq_lowercase(s: str) -> list[int]:
    cnt = [0] * 26
    for ch in s:
        if ch.islower():
            cnt[ord(ch) - ord('a')] += 1
    return cnt


print(freq_lowercase('abca'))

Common mistakes

• Off-by-one on alphabet size (need length 26 vs 128).
• Using arrays when key universe is huge—memory blow-up.

Key takeaways

• Pair frequency arrays with prefix sums for range frequency in static arrays.
• For sliding windows, combine count array with two pointers.