Counting, Grouping & Complements

Arrays & Hashing, lesson 2 of 3

Counting, Grouping & Complements

Four reusable hash-map templates: count, group by key, look up a complement, bucket by frequency.

14 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Almost every hashing problem is one of four moves:

  1. Count things: Counter / dict.get
  2. Group things by a shared key: defaultdict(list)
  3. Look up a complement: "have I seen the value that completes this one?"
  4. Bucket by frequency to avoid sorting

Learn these as templates and you'll recognise them instantly.

Example

1. Counting

Counter is a dict subclass: missing keys read as 0, and two Counters compare equal when every count matches, which is exactly an anagram check.

Quiz

What does this print?

2. Grouping by a canonical key. When items belong together if they share some property, compute that property as a hashable key and collect items under it. For anagrams the key is the sorted letters: "tea", "eat" and "ate" all sort to "aet".

Example

2. Group by key

defaultdict(list) creates an empty list the first time a key is used, so there's no "if key not in groups" dance. Try grouping by len(w) or w[0] instead.

3. Complement lookup. To find two numbers that add up to target, don't search for a partner for every number. Walk once, and for each x ask the dict: "have I already seen target - x?" Store what you need to answer (usually the index).

Example

3. Complement lookup, traced

At i=3 we need 3, and the dict already knows 3 lives at index 1. One pass, O(n). Change the target to 100 to see the "not found" path.

4. Bucket sort by frequency. "Return the k most frequent" tempts you to sort by count: O(n log n). But a count can never exceed n, so make n + 1 buckets where buckets[c] holds the values seen exactly c times, then read from the top down. That's O(n).

Example

4. Buckets by frequency

The bucket index is the count, so walking from the right end gives values from most to least frequent, with no comparison sort at all.

Quiz

What does this print?

Exercise

First unique character

Write first_unique(s) that returns the index of the first character that appears exactly once in s, or -1 if there is none.

  • first_unique("swiss") is 1 ("w")
  • first_unique("aabb") is -1

Two passes: count first, then scan for the first count of 1. Aim for O(n).