CodeWithYash

Foundation · Module 5 · Lesson 3

Frequency counting

Histograms for strings, arrays, and multisets.

15–25 min readLesson 29 of 123

Lesson 29 of 123

1d streak

The Histogram Mental Model: Frequency Arrays vs HashMaps

Counting the occurrences of elements transforms unstructured strings or sequences into frequency signatures. In coding interviews, recognizing whether to use a fixed array (int[26]) or a hash map determines whether your solution runs in optimal memory.

Frequency Counting: Array int[26] vs HashMap
Word: "banana"

Frequency Array int[26]:
Index:   0 ('a')    1 ('b')    13 ('n')
Count:      3          1          2
(All other indices are 0)

Memory Cost: Exactly 26 integers (104 bytes) on stack/heap!
Speed: 10x faster than HashMap (direct array offset arithmetic, zero boxing, zero hash computation).

Architectural Boundary · Do Not Confuse

Concept A

Fixed Alphabet: int[26] or int[128]

Concept B

Arbitrary Keys: HashMap<K, Integer>

Use fixed frequency arrays when keys are ASCII characters or lowercase English letters. Use HashMap only when the key domain is unbounded (arbitrary words, large integers, objects).

Cost Model

Complexity & Trade-offs

Count n values
Expected O(n)
O(k)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Presence, uniqueness, frequency, complement, and previously seen state queries.
  • Replacing repeated scans with indexed history.
  • Grouping values by a canonical key.

Common mistakes

  • Assuming hash lookup has a deterministic O(1) worst case.
  • Updating the map before a query that requires a distinct earlier item.
  • Using mutable or inconsistent keys.

Practice prompts

  • Reproduce the worked Frequency counting example without looking at the trace.
  • Change one input condition and explain whether the Frequency counting invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.