47. Who Is Smaller
In a quiz, each student's score is stored in nums. For every student, work out how many other students scored strictly lower.
Return an array answer of the same length as nums, where answer[i] is the number of positions j with nums[j] < nums[i].
Scores are small whole numbers, so you do not need to compare every pair. Tally how often each score occurs, turn the tally into a running total, and look each student up in it; this is the idea behind counting sort.
Example 1
- Input:
- nums = [9,4,4,7,2]
- Output:
- [4,1,1,3,0]
- Explanation:
9 beats four scores, each 4 beats one, 7 beats three, and 2 beats none, giving [4, 1, 1, 3, 0].
Example 2
- Input:
- nums = [7,7,7]
- Output:
- [0,0,0]
- Explanation:
Nobody scored lower than anyone else, so every answer is 0.
Constraints
1 ≤ nums.length ≤ 500
0 ≤ nums[i] ≤ 100
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n + k) where k = 101
- Space
- O(k)