Arrays and Hashing
10 / 170Arrays and HashingLesson 5 of 10About 37 min
Two phases. Counting is easy. Picking the top k without sorting everything is the interesting half.
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.
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.
Time and space for sort_scores, in terms of n, the number of entries. The score range is fixed at 0 to 100.
def sort_scores(scores): buckets = [[] for _ in range(101)] for name, score in scores: buckets[score].append(name) ordered = [] for score in range(100, -1, -1): for name in buckets[score]: ordered.append((name, score)) return orderedRead 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.