Skills101
← All coding problems

Minimum Swaps to Sort

mediumArrays & Prefix Sums+20 XPTime limit 2s

Students with different heights stand in a line. In one move you may swap any two students (not only neighbours). What is the minimum number of swaps to arrange them in increasing order of height?

Input:

  • line 1: n
  • line 2: n distinct integers (the heights, in line order)

Output: the minimum number of swaps.

Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ a[i] ≤ 10⁹, all values distinct.

Think about it: sort a copy to learn where each element must go. Following "element at i belongs at j" splits the positions into cycles. A cycle of length L needs exactly L − 1 swaps, so the answer is n − (number of cycles).

Sample input 1

5
101 758 315 730 472

Sample output 1

2

Sample input 2

4
4 3 2 1

Sample output 2

2

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.