Skip to content
BytePatterns

Frequency Counting

Hash Tables: lesson 3 of 5

One pass, one counter per distinct value.

Lesson 3 of 5 · 4 min

Frequency Counting

Step 1 of 9

Counting is one notebook line per species — never a fresh page, and never a second walk down the route.

The Idea

A surprising number of questions collapse into counting: the most common item, the first value that repeats, whether two collections hold the same multiset. Build a map from value to count in one pass, then read the answer off the map. Rescanning the list per item would cost O(n²).

Real-World Example

A dawn bird survey volunteer walks a fixed route with one notebook line per species. Every sighting is a tick beside an existing name, never a fresh page. When the route ends the totals are already finished, and no stretch of path is ever walked twice.

The Code

def top_item(items):
    counts = {}
    for item in items:
        # first sighting starts at 0, every later one adds a tick
        counts[item] = counts.get(item, 0) + 1
    return max(counts, key=counts.get)     # highest tally wins

birds = ["robin", "crow", "robin", "wren", "crow", "robin"]
print(top_item(birds))          # robin
print(len(set(birds)))          # 3 distinct species

Your turn

Put the steps in the right order.

  1. Return the key holding the largest count
  2. Create an empty counts map
  3. Add one to that value's count
  4. Take the next element from the list

Mini quiz

1 / 3

Cost of building a frequency map over n items?