Arrays & Hashing

Counting & Grouping

Frequency maps and canonical keys to count, compare or group items.

Easy, about 60 minutes to practise.

1Understand

The idea

Count occurrences with a frequency map, or map each item to a canonical key (sorted letters, a tuple of counts) so that items that should be grouped together share the same key. Two collections are "the same up to order" exactly when their counts match.

Intuition

Counting problems ask how often something appears; grouping problems ask which items share a property. Both start from a frequency map or a canonical key that makes equivalents look identical (sorted letters, a 26-tuple of counts, a frozenset).

Two collections are the same up to order exactly when their counts match. Counter makes that comparison one line; a hand-built dict is the same idea.

Choose the cheapest key that distinguishes groups: sorting a string is O(k log k); a count tuple over a fixed alphabet is O(k).

What you will be able to do

  • Build frequency maps
  • Design a canonical key (sorted string, count tuple)

When to use it

  • Anagrams or permutations of each other
  • Most / least frequent
  • Group items that share a property

2See it

Walkthrough

Group anagrams by key

words = ["eat", "tea", "tan"], canonical key = sorted letters.

1 / 4

i
eat
tea
tan
012
i → index 0

groups

  • ∅ empty

Empty groups. For "eat", key = "aet".

key = "".join(sorted(item))

Live template

Line 3 active

1groups = defaultdict(list)
2for item in items:
3 groups[canonical_key(item)].append(item)

Complexity: time O(n·k), space O(n)

Building groups is O(n · cost(key)). Space is O(n) to hold the items. Fixed-alphabet count keys beat sorting when k is large. If you only need the most frequent key, a heap or bucket sort on frequencies can avoid a full sort of n items.

Read the walkthrough as text

Group anagrams. Words ["eat","tea","tan","ate","nat","bat"].

  1. For each word, build key = tuple(sorted(word)) (or a 26-length count tuple).
  2. Append the word to groups[key].
  3. After one pass, the map values are the groups: {('a','e','t'): ["eat","tea","ate"]...}.

Valid anagram of two strings is the special case with one group of size two: compare two Counters (or one count array incremented then decremented to all zeros).

3Recognise it

Kinds of problems (5)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Frequency comparison (valid anagram)

    Example. Are two strings permutations of each other?

    How. Count each letter with Counter (or a size-26 array); equal multisets ⇔ anagram.

  • Grouping by canonical key

    Example. Group strings that are anagrams.

    How. Key = sorted(s) or tuple of counts; defaultdict(list) buckets items with the same key.

  • Majority or most frequent element

    Example. Element that appears more than n/2 times, or top frequent words.

    How. Count once, then scan counts or use a heap / bucket by frequency for top-k.

  • Bucket sort by frequency

    Example. Sort array by how often each distinct value appears.

    How. freq[value] → index into buckets; walk buckets from high frequency to low.

  • Counting pairs with a property

    Example. Number of equal-value pairs, or pairs with a given difference.

    How. As you scan, add count[need] to the answer, then increment count[current].

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Unhashable key

    Why it happens. A list or dict is used as a dict key when grouping.

    How it fails. groups[[1,2]] = … raises TypeError: unhashable type: list.

    Fix. Convert to tuple, frozenset, or string key before using as dict key.

  • Count comparison

    Why it happens. Comparing two Counter objects or maps after partial updates.

    How it fails. Anagram check returns true when one map still has a letter the other never had (missing key treated as zero incorrectly).

    Fix. Compare counts for every letter in the union of keys, or use Counter subtraction and test emptiness.

  • Expensive key

    Why it happens. Sorting every string as the key is simpler mentally but costly per item.

    How it fails. n strings length k each: sorting all n keys costs O(n·k log k) where a count tuple is O(k).

    Fix. Use tuple(counts) or Counter; sort only when the key must be canonical and k is tiny.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons