A shunting yard holds n freight cars sitting in a single row on one track, each bearing a distinct identification number. The yard crew can uncouple and swap only two cars that are directly next to each other on the track; each such adjacent swap counts as one recoupling operation. The dispatcher wants the cars arranged left to right in strictly increasing order of their ID numbers. Determine the minimum number of adjacent recoupling operations required to achieve this.
n — the number of cars.n distinct integers a_1, a_2, ..., a_n — the ID numbers of the cars, listed from the front of the track to the back.A single integer: the minimum number of adjacent swaps needed to sort the cars into strictly increasing order.
Example 1
Input
3 3 1 2
Expected
2
Explanation
The cars sit in order 3, 1, 2. The out-of-order pairs (inversions) are (3,1) and (3,2), giving 2 inversions total. Sorting with adjacent swaps: swap cars 3 and 1 to get 1, 3, 2 (one swap), then swap cars 3 and 2 to get 1, 2, 3 (a second swap). That is exactly 2 swaps, and no sequence of fewer swaps can fully sort this row.
Example 2
Input
5 5 4 3 2 1
Expected
10
Explanation
The row is fully reversed, so every one of the C(5,2) = 10 pairs of cars is out of order, giving 10 inversions. Sorting a fully reversed row of n cars using only adjacent swaps always takes exactly n(n-1)/2 swaps, which for n = 5 is 5*4/2 = 10.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →