The problem
For every position i of a list of numbers, count the positions j > i with values[j] < values[i]. Return the counts as a list of the same length.
smaller_after([5, 2, 6, 1]) # [2, 1, 1, 0]
smaller_after([3, 3, 3]) # [0, 0, 0]: equal is not smaller
The counts add up to the number of inversions of the list (lesson 3). The values may be negative and may repeat.
Limits
- Up to 200,000 values, in any order, including an order that is already sorted. Aim for O(n log n).
Builds on DVCQ-3 Counting inversions.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
8 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | No values | Not run | |
| 3 | One value | Not run | |
| 4 | All equal | Not run | |
| 5 | Falling | Not run | |
| 6 | Repeats and negatives | Not run | |
| 7 | Already in order, 200,000 values | Not run | |
| 8 | 120,000 scattered values | Not run |