Group records and invert a dictionary

Group with setdefault or defaultdict(list) — one pass, one lookup per record, no scanning for an existing group. Inverting is a one-line comprehension, with two traps: duplicate values silently collapse, and unhashable values raise.

Dicts, sets & hashingCoding problemEasy

Step through it

What to watch

  • Each record costs one lookup and one append.
  • Groups appear as they are first encountered.
  • Inversion assumes the values are unique — watch what happens when they are not.

Say this out loud

"defaultdict(list) and append - one pass, O(n). For inverting, a dict comprehension, but I'd check the values are unique first, because duplicates silently overwrite and you lose entries without an error."

Overview

Grouping collects records under a shared key; inversion maps each value back to the keys that used it. Grouping needs lists because many records can share a key, and inversion needs a collection when values repeat.

In this guide
  1. Run it: Group records and invert a dictionary in code
  2. The defaultdict trap
  3. Inverting a dictionary
  4. Three ways to group
  5. Two ways inversion breaks
  6. Where this shows up
  7. itertools.groupby and why it surprises people
  8. The grouping patterns worth having ready
  9. Sources and next steps

Run it: Group records and invert a dictionary in code

The three grouping idioms agreeing, groupby getting it wrong on unsorted input, and both inversion failures caught in the act.

1Python
Output

Inverting has its own two traps: duplicate values collapse silently, and values that cannot be hashed cannot become keys.

2Python
Output

The defaultdict trap

A defaultdict creates entries on read. Merely looking a key up inserts it:

3Python
Output

That surprises people debugging a size or an iteration. Two ways to avoid it: use d.get(key, []) for reads, or convert to a plain dict once building is finished with dict(d).

The related habit worth having: never pass a defaultdict out of a function as a return value if callers will read arbitrary keys. Convert it first, and the mutation-on-read behaviour stays inside the code that wanted it.

Inverting a dictionary

4Python
Output

Duplicate values collide, and the last one wins. alice and carol are both 30, so only carol survives. This is the single most common bug with inversion, and the fix is to invert into lists:

5Python
Output

Which is the same operation as grouping — grouping the keys by their value. The two topics are one topic.

The other requirement: values must be hashable to become keys. Inverting {"a": [1, 2]} raises TypeError, and converting the list to a tuple first fixes it.

Three ways to group

setdefault(key, []).append(x) — no import, and it makes the default explicit. It does construct an empty list on every call, which is why the next form is usually preferred.

defaultdict(list) — the idiomatic answer. Remember that reading a missing key creates it, so it is not safe to inspect casually.

itertools.groupby — the one that catches people. It groups consecutive equal keys only, so it needs the input sorted by the same key first. It is not the SQL GROUP BY its name suggests.

Two ways inversion breaks

Duplicate values. {v: k for k, v in d.items()} keeps only the last key for each repeated value, silently. If duplicates are possible, invert to lists instead — which is just grouping again, by value.

Unhashable values. A value that was fine as a value cannot necessarily be a key: a dict mapping names to lists of scores cannot be inverted directly, because a list is unhashable.

Where this shows up

Grouping is the shape behind most "organise this data" questions. Anagram groups keyed on sorted letters. Files keyed on their hash. Log lines keyed on their level. Spot the shape and you skip the nested loop that scans for an existing group.

The one-pass defaultdict build is O(n). A nested loop that re-scans the groups already built is O(n²). On a hundred thousand records that is ten thousand operations versus ten billion. The gap is why this idiom is worth reaching for on sight.

itertools.groupby and why it surprises people

The standard library has a groupby, and it does not do what the name suggests to anyone coming from SQL or pandas.

6Python
Output

itertools.groupby groups consecutive runs only. It does not collect scattered items. To get SQL-like behaviour the input must be sorted by the same key first:

7Python
Output

Which costs O(n log n), while the defaultdict version is O(n). Prefer defaultdict unless the data is already sorted or the runs themselves are what you want. Compressing repeated values, detecting consecutive duplicates, run-length encoding.

The other sharp edge: the group is an iterator sharing the underlying stream. It is exhausted as soon as you advance to the next group, so list(group) must happen before moving on. groups = [(k, g) for k, g in groupby(x)] yields empty groups for exactly this reason.

The grouping patterns worth having ready

Group by a computed key.

8Python
Output

Group by several keys — use a tuple:

9Python
Output

Count instead of collect — Counter is the specialised form:

10Python
Output

Aggregate while grouping — defaultdict(int) for sums, defaultdict(set) for deduplicated members:

11Python
Output

Group anagrams, the classic interview form — the key is a canonical form:

groups = defaultdict(list)
for w in words:
    groups["".join(sorted(w))].append(w)
return list(groups.values())
NeedTool
Collect itemsdefaultdict(list)
Count itemsCounter
Sum valuesdefaultdict(int)
Deduplicated membersdefaultdict(set)
Nested groupingdefaultdict(lambda: defaultdict(list))
Consecutive runs onlyitertools.groupby

The nested case needs a lambda because defaultdict(defaultdict(list)) is wrong — the argument must be a callable that produces the default, not an instance.

For the underlying ideas, see dictionaries, dictionary methods and dict comprehensions.

Sources and next steps

How the code works

The three grouping idioms agreeing, groupby getting it wrong on unsorted input, and both inversion failures caught in the act.

How the code works

  1. setdefault(team, []).append(name)One lookup and one append per record. The alternative — scanning existing groups for a match — is the O(n²) this idiom exists to avoid.
  2. groupby(people, key=...)Groups only consecutive equal keys, so unsorted input produces a group per run and later runs overwrite earlier ones. Sorting first is mandatory.
  3. {v: k for k, v in sizes.items()}Silently loses ana, because two names share a size and the later key wins. No error, one entry gone.
  4. {v: k for k, v in scores.items()}A TypeError: the values are lists, and a key must be hashable. Converting to tuples is the usual fix.

Change one thing

  • Group by two fields at once using a tuple key. It works because tuples are hashable — the same reason they can be dict keys at all.
  • Read a missing key from the defaultdict and print it again. The read created an entry, which is the trap that idiom carries.

Where this runs

Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.

Check yourself

0 of 3

Answer without scrolling back up.

  1. itertools.groupby differs from SQL's GROUP BY in that it:

  2. Inverting a dict with a comprehension when two keys share a value:

  3. A dict mapping names to lists of scores cannot be inverted directly because:

Cheat sheet

Group records and invert a dictionary

Group records by a shared field and invert a dictionary so values become keys. See both operations in plain Python and with defaultdict.

INTERVIEW · vizlearn.in/interview/grouping-and-inverting-dictionaries.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Teaching a course with this? Individual teachers can use it freely; for a whole department or programme, see institutional licences.