Count or sort: choosing a frequency tool

Arrays, strings and hash maps Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
from collections import Counter
c = Counter("mississippi")
print(c.most_common(2))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [('i', 4), ('s', 4)]

Right: i and s both appear 4 times, and i was seen first.

Equal counts keep the order items were first counted, which is why 'i' (index 1) leads 's' (index 2).

Why not the others?
  • B [('s', 4), ('i', 4)]. Ties keep first-seen order, and i comes before s in the word.
  • C [('s', 4), ('p', 2)]. i also appears 4 times, more than p.

30-second answer

Counting with a dict or Counter is O(n) time and O(distinct) space and keeps the original order. Sorting is O(n log n) time but can use O(1) extra space in place and makes equal items neighbours. Prefer counting by default; sort when memory is tight, when you also need order, or when items are not hashable.

Practise saying it · 45 s. No recording, just a timer

Compare counting and sorting for frequency questions.

Say your answer out loud, then check which of these points you covered:

  • O(n) count vs O(n log n) sort
  • Space and order trade-offs
  • Pick by constraint

Deep dive

Top k by count: Counter.most_common(k) uses a heap for small k, O(n log k) after counting.

Comparing two strings as letter bags: compare counts in O(n), or compare sorted strings in O(n log n).

Sorting is stable in Python (Timsort), so ties keep their input order, which helps 'first wins' rules.

Common mistakes

  • Sorting just to count, which costs log n extra for no gain.
  • Assuming most_common breaks ties alphabetically: equal counts keep the order items were first seen.

Senior take & follow-ups

Good answers compare both options on time, space and order, then pick one for the stated constraints.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if the data does not fit in memory?

    Show hint

    External sort, or count in chunks and merge counts if distinct values fit.

  2. When is a fixed array better than a dict?

    Show hint

    When keys are small integers or letters: a list of 26 counts has less overhead.

What each operation costs: Arrays · Dynamic Arrays · Hash Table · Hash Functions

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.