Arrays and Hashing
Count, then select
Two phases. Counting is easy. Picking the top k without sorting everything is the interesting half.
Two phases
Problems of this shape split cleanly. Phase one summarizes the input, usually into a frequency map, which you can already write. Phase two picks the winners out of that summary. Phase two is where the interesting choice lives.
The obvious way to pick winners is to sort the summary and take from the top. For m distinct values that is O(m log m). It is a perfectly good answer and you should say it out loud before improving on it.
Why it works
Sorting is not the only way to order things
Here is the observation that beats a sort. If the values you would sort by are integers in a known narrow range, you do not have to compare them. You can use the value itself as an index.
Concretely: to sort exam scores that are always 0 to 100, make a list of 101 buckets, drop each score into bucket[score], then read the buckets in order. Every score is placed in constant time and reading back is a single walk. Linear, no comparisons.
Tip
The condition that makes it legal
This is counting sort, and it only works because the sort key is a bounded integer. If scores could be any real number you would be back to comparisons.
So the question to ask of any counting problem is: what is the largest the thing I am ordering by could possibly be? If the answer is a small bound you can name, indexing beats sorting. If someone asks how you beat the O(m log m) comparison bound, the answer is that you did not beat it, you stopped comparing.
Stopping early
When you only want the top few rather than the whole ordering, the downward walk can stop as soon as it has collected enough. That is worth noticing because it changes nothing about the setup and removes most of the work.
Tip
The third option, for later
There is also a middle approach: keep only the best k seen so far in a heap, which costs O(m log k) and wins when k is tiny compared to m. Heaps get their own unit, and Counter.most_common(k) does this for you in the meantime.
Being able to name all three and say which fits the constraints is a much stronger answer than producing one by reflex.
Cost of bucketing
Time and space for sort_scores, in terms of n, the number of entries. The score range is fixed at 0 to 100.
Time
Space
Top K Frequent Elements
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.