1341. Stable Counting Positions
A bakery tags trays with small integer codes and wants to know where each tray will end up once the trays are lined up in ascending code order. Given the array nums, return an array res of the same length where res[i] is the 0-based position at which nums[i] lands after a stable ascending sort. Stable means that trays with equal codes keep the order in which they appear in the input, so of two equal codes the earlier index gets the smaller position.
Every position from 0 to n-1 appears exactly once in the answer. The values are small (at most 10000), so use counting: count each value, turn the counts into starting slots with a prefix sum, then scan nums from left to right handing out slots. Target O(n + 10000) time and O(10000) extra space.
Example 1
- Input:
- nums = [3,1,2,1,3]
- Output:
- [3,0,2,1,4]
- Explanation:
The stable order is index 1, 3 (value 1), index 2 (value 2), index 0, 4 (value 3), so the positions are 3, 0, 2, 1, 4.
Example 2
- Input:
- nums = [5,5,5]
- Output:
- [0,1,2]
- Explanation:
All values are equal, so they keep input order and take positions 0, 1, 2.
Example 3
- Input:
- nums = [0,10000,0]
- Output:
- [0,2,1]
- Explanation:
Both zeros come first (indices 0 and 2) and the 10000 comes last, so the positions are 0, 2, 1.
Constraints
- 1 ≤ n ≤ 1000
- 0 ≤ 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.
Expected complexity
- Time
- O(n + V)
- Space
- O(V)