The problem
A train has coaches of three classes, written as 0, 1 and 2. Rearrange the list coaches in place so that every 0 comes first, then every 1, then every 2. “In place” means you change the list you were given, by swapping values inside it. You do not build a new list.
c = [2, 0, 1, 2, 0]
sort_coaches(c)
c # [0, 0, 1, 2, 2]
sorted and .sort() are switched off for this problem. Use one pass and three positions in the list. The point is the invariant: write down what is true of each part of the list at the start of every pass.
Limits
- Up to 300,000 coaches. Each value is 0, 1 or 2.
- The tests read the list after your function returns.
Builds on CORR-2 Loop invariants.
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.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | A short train | Not run | |
| 2 | Already in order | Not run | |
| 3 | Reversed | Not run | |
| 4 | Only 1s and 2s | Not run | |
| 5 | One coach | Not run | |
| 6 | Empty train | Not run | |
| 7 | Same list object | Not run | |
| 8 | 300,000 coaches | Not run |