vizlearn

Count things with a dictionary

Interview QuestionsBy Updated

Four ways to write the same loop — get, setdefault, defaultdict and Counter — all O(n). For the k most common, do not sort everything: a heap of size k gives O(n log k), which matters when n is huge and k is ten.

Overview

Four ways, and which to use

Counting occurrences is the most common dictionary task, and Python offers four spellings.

1Python
Output
All four are O(n). Counter is idiomatic, C-optimised for iterables, and comes with most_common. Use it unless there is a reason not to.
defaultdict(int) is right when counting happens as part of a larger loop that does other work. dict.get is right when you want a plain dict in the output — Counter and defaultdict are dict subclasses and mostly interchangeable, and they are not identical.

                

            
Dicts, sets & hashingCoding problemEasy

        


        

            
Step through it

            

            

                

                    
                    

                        

                        

                        

                        
                        

                            
                            
                            
                            
                            
                        

                    

                

                
What to watch
  • Each item costs one lookup and one write, whatever the dictionary holds.
  • The counter grows only with distinct items.
  • Nothing is ever searched for.
Say this out loud
"Counter for the counting. For top-k I'd use heapq.nlargest rather than sorting - O(n log k) instead of O(n log n), which is the difference that matters when n is a billion."

            

        


    


    
        
    

    
    

        


            

                
Count things with a dictionary

                
Count the frequency of each item in a sequence. Now find the k most common.

            

            

                
                

                    
Run it

                    
The four idioms producing identical counts, the defaultdict read trap caught in the act, and top-k timed three ways on a large input.
2Python
Output

                

                

                    
What Counter adds

                    
3Python
Output
The c["z"] behaviour is the difference from defaultdict: Counter returns 0 for a missing key without inserting it, where defaultdict inserts a 0 entry. That matters when iterating — reading a missing key from a defaultdict during a loop changes its size.
The a - b behaviour is the trap: subtraction discards non-positive counts. Use c.subtract(other) to keep negatives.

                

                

                    
The everyday patterns

                    
Most frequent element:
4Python
Output
Anagram check:
5Python
Output
Are all characters unique?
6Python
Output
Elements appearing more than k times:
7Python
Output
Counting by a derived key:
8Python
Output
That last one is worth noting: Counter accepts any iterable, so a generator expression counts by any computed key without materialising an intermediate list.

                

                

                    
The four idioms

                    
counts[x] = counts.get(x, 0) + 1 needs no import and makes the default explicit. counts.setdefault(x, 0) is the same idea and reads worse for counting. defaultdict(int) lets you write counts[x] += 1 directly. Counter(seq) does the whole loop in C.
They are all O(n). Reach for Counter in real code and be able to write the get version when an interviewer asks you not to import anything.

                

                

                    
One trap in defaultdict

                    
Reading a missing key from a defaultdict creates it. if counts[x] > 5 silently inserts x with value 0, so a loop that only reads can grow the dictionary without anyone noticing.
Use .get() or in when you are only asking. Counter does not have this problem: reading a missing key returns 0 without inserting.

                

                

                    
Top-k without sorting

                    
Sorting all the counts is O(m log m) in the number of distinct items. Keeping a heap of size k is O(m log k), which is what heapq.nlargest and Counter.most_common(k) do.
For "top 10 of a billion" that is the difference between a practical job and an impossible one, and it is the answer the question is actually fishing for. Bucket sort by count is O(m) when the counts are bounded — worth mentioning as the linear option.
Put numbers on it. With a billion distinct items and k = 10, sorting everything is about 10⁵ × 30 ≈ 3 × 10¹⁰ comparisons; a size-10 heap is about 10⁵ × 3.3 ≈ 3.3 × 10⁹ — roughly nine times fewer — and the bucket-sort option is a flat 10⁵. The heap also holds ten items instead of a billion, so the memory difference is the part that actually decides whether the job runs at all. Counter.most_common(k) uses exactly this heap internally, so the idiomatic call and the hand-rolled heapq.nlargest are the same algorithm — and both beat sorted(counts.items())[:k], which pays the full sort for a slice you throw most of away.

                

                

                    
Grouping, the sibling problem

                    
Counting collapses items to a number; grouping keeps them.
9Python
Output
defaultdict(list) creates an empty list on first access, which removes the "if the key is absent, initialise it" branch. Without it:
10Python
Output
itertools.groupby is the one to be careful with: it groups consecutive equal items, so the input must be sorted by the same key first. Using it on unsorted data produces many small groups and is a common surprise.
11Python
Output
defaultdict needs no sorting and is usually the better choice.

                

                

                    
Counting in a sliding window

                    
The incremental form, which appears in several interview problems:
12Python
Output
The del is essential. A Counter holding {'a': 0} does not compare equal to one without the key, so leaving zero entries breaks the comparison. That is the single most common bug in window-counting solutions.

                

                

                    
Edge cases and gotchas

                    
CaseBehaviour
Counter([])Empty counter; most_common() returns []
max(counts.values()) on emptyValueError — guard it
Ties in most_commonInsertion order among equals; not documented as stable
counts["missing"]0 from Counter, inserts 0 in defaultdict
Unhashable itemsTypeError — convert lists to tuples
Counting floats0.1 + 0.2 is not 0.3; round first
c - otherDrops non-positive counts; use subtract
The ties row is worth knowing: most_common sorts by count, and elements with equal counts appear in the order first encountered. That is current behaviour rather than a guarantee, so do not depend on it for correctness.

                

                

                    
Questions people ask

                    
Counter or defaultdict? Counter for pure counting; defaultdict(int) when counting is part of a larger loop; defaultdict(list) for grouping.
Is Counter faster? For counting a whole iterable, yes — the loop is in C. For incremental += 1 in Python, they are comparable.
Why does c["missing"] return 0? Counter defines __missing__ to return 0 without inserting, which makes counting code cleaner.
Why did my Counter comparison fail? Zero-valued keys. Delete them when a count reaches zero.
How do I count by a field? Counter(x.field for x in items).
Is a Counter a dict? A subclass, so all dict operations work — and it is not hashable, so it cannot itself be a dictionary key.

                

                

                    
Recap in one screen

                    
  • Counter(iterable) is the idiomatic count; defaultdict(list) is the idiomatic grouping.
  • Counter returns 0 for missing keys without inserting; defaultdict inserts.
  • Delete zero-valued keys before comparing Counters, or equality fails.
  • Counter subtraction drops non-positive counts — subtract keeps them.
  • itertools.groupby needs the input sorted by the same key; defaultdict does not.

                

            


        

    



How the code works
The four idioms producing identical counts, the defaultdict read trap caught in the act, and top-k timed three ways on a large input.
How the code works
  1. counts.get(x, 0) + 1The version to write when told not to import anything. The default removes the "first time?" branch without hiding what is happening.
  2. d["never_added"] > 5A read that inserts. defaultdict creates on any missing lookup, so a loop that only inspects can grow the dictionary silently.
  3. heapq.nlargest(k, ...)Keeps a heap of size k rather than sorting m items: O(m log k). Counter.most_common(k) does the same thing.
  4. Counter(big)One pass in C. The counting is never the bottleneck — the question is always what you do with the counts afterwards.
Change one thing
  • Raise the value range to 5,000,000 so nearly every item is distinct. The sort/heap gap widens as m grows.
  • Implement top-k with bucket sort by count. O(m) when counts are bounded, which beats both.
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. Reading a missing key from a defaultdict:
  2. Finding the k most common items is best done with:
  3. Counting n items with a dictionary costs:





 Cheat sheet
Count things with a dictionary
Four ways to write the same loop — get, setdefault, defaultdict and Counter — all O(n). For the k most common, do not sort everything: a heap of size k gives O(n log k), which matters when n is huge and k is ten.
INTERVIEW · vizlearn.in/interview/counting-with-dictionaries.html
More in Interview
InterviewWhat is the complexity of this code?InterviewDesign an LRU cacheInterviewLongest consecutive sequenceInterviewSubarray sum equals k
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.
About VizLearnGitHubLinkedInContact