Tally-Sort Exam Scores
EasySorting & SearchingFree
Problem
A testing centre stores every candidate's score as an integer from 0 to 100. Hundreds of thousands of scores arrive at once and must be listed from lowest to highest.
Given the array scores, return the scores sorted in non-decreasing order in linear time.
Example 1
- Input:
- scores = [88, 42, 100, 42, 0]
- Output:
- [0, 42, 42, 88, 100]
Count each score (0 once, 42 twice, 88 once, 100 once) and write them back from 0 up to 100.
Example 2
- Input:
- scores = [55]
- Output:
- [55]
Constraints
- 0 ≤ scores.length ≤ 10^6
- 0 ≤ scores[i] ≤ 100
Hint
Show the first hint
Only 101 different values can appear. Does a comparison sort really need to compare them?
Walkthrough
How to approach it
01Clarify before coding
- Is the range really fixed at 0..100? Yes, which is what makes a counting approach possible.
- Can the array be empty? Yes: return an empty array.
- Do the scores carry extra data that must stay attached? No, they are plain integers, so rebuilding the values from counts is enough.
02Brute force
Call a comparison sort (merge sort, the built-in sort).
Cost: O(n log n) time: correct, but about 20 comparisons per element for n = 10^6 when the range offers something cheaper.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.