526. Smaller to My Right
A line of runners waits at the start gate, each wearing a bib number given by nums, in order from the front of the line to the back. Every runner wonders how many people behind them wear a strictly smaller bib number.
Return an array res of the same length as nums where res[i] is the number of indices j > i with nums[j] < nums[i]. Equal numbers do not count. For a single runner the answer is [0].
Example 1
- Input:
- nums = [6,2,8,1,5]
- Output:
- [3,1,2,0,0]
- Explanation:
Behind 6 there are three smaller bibs (2, 1, 5), behind 2 one (1), behind 8 two (1, 5), and nobody smaller behind 1 and 5.
Example 2
- Input:
- nums = [3,3,-1,3]
- Output:
- [1,1,0,0]
- Explanation:
The first 3 only has -1 smaller behind it (the other 3 is equal and not counted); the second 3 also counts only -1.
Constraints
1 ≤ nums.length ≤ 105
-104 ≤ nums[i] ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n log V)
- Space
- O(V)