defaultdict
A lot of interview problems need you to build up a collection keyed by something you haven't seen yet: group words by their first letter, group people by age, build a graph's adjacency list. With a plain dict, the first time you touch a new key you have to check for it and create it yourself. defaultdict, from the collections module, does that check for you.
What defaultdict does
O(1)defaultdict takes a factory function, a function with no arguments that produces a default value. The moment you look up a key that isn't there, it calls the factory, stores the result under that key, and hands it back to you. Group words by their first letter with defaultdict(list):
No if key not in groups check anywhere. The first time a letter shows up, list() runs, creates an empty list, and .append() adds to it, all in one line.
defaultdict vs dict.get() vs setdefault()
The same grouping works with a plain dict two other ways. With dict.get(), you build a new list and reassign it every time:
With setdefault(), one line does the check-and-create that the if block above spells out:
Note
All three give the same result. defaultdict reads best when you're doing this kind of insert repeatedly in a loop and don't want the setup logic in your way. setdefault() is a reasonable middle ground when you don't want to import anything, though it re-runs the default expression, here [], on every single call, even when the key already exists. dict.get() is the right tool when you're only reading, with a fallback, and don't intend to insert anything into the dict at all.
The gotcha: reading a missing key inserts it
watch outBecause defaultdict can't tell a read from a write, any lookup of a missing key creates it, even one that's just checking a condition:
Note
counts["missing"] inside the if never printed "truthy" (0 is falsy), but it still inserted "missing" into the dict with a default value of 0. The dict grew from empty to one entry just from being read. If you need to check whether a key exists without creating it, use "missing" in counts instead of indexing.
Nested defaultdicts
A factory function can itself return a defaultdict, which gives you a structure that creates itself at every level. This is the standard way to build a weighted adjacency list:
Note
graph["a"]["b"] += 1 works with no setup: the outer defaultdict creates an inner defaultdict(int) for "a", and that inner one creates a 0 for "b" before adding 1 to it. And the same gotcha from above still applies at both levels: printing graph["z"] above created a brand new, empty entry for "z" in the outer dict, just by asking for it.
Converting back to a plain dict
dict() copies a defaultdict's current contents into a regular dict that no longer auto-creates missing keys:
Note
The real reason to convert before handing a defaultdict off to other code: whoever holds the original can still create new keys in it just by reading, the same gotcha covered above. Convert it with dict() first and a missing-key lookup raises a normal KeyError instead, the same as it would on any other dict.
Where defaultdict shows up in interviews
The single biggest use case is building an adjacency list for a graph: defaultdict(list) lets you add an edge with graph[a].append(b) without first checking whether a has shown up before.
- Graph Breadth First Search and Graph Depth First Search both usually start by building an adjacency list this way, before the traversal logic even begins.
- Clone Graph uses a
defaultdict-style mapping from original node to cloned node, so each node gets cloned exactly once no matter how many edges point to it.
Beyond graphs, any "group these by that" problem, anagram grouping, bucketing by a computed key, tallying with defaultdict(int), is a case for reaching for defaultdict before writing a manual if key not in d check.