Can anyone share their approach with proof if any ? I am unable to understand the editorial
Lets look at the case where k < n/2. In this case, for every position, you can always swap it with one of the two extreme positions ie., 1 and n. So, for the first (smallest) number, if its already in a position where it can be swapped with the first position, you’ll swap it. Else, you’ll swap it with the nth position and then swap with position 1.
Following this process, suppose that you already moved the smallest ‘i’ numbers to the first ‘i’ positions. Now, you need to move the next smallest number to position ‘i+1’, Now, at least one of the extreme positions will be swappable with i+1 (by swappable, I mean that the distance will be > k), suppose that this extreme position is ‘n’, then you need to first bring your number to position ‘n’. If your number is swappable with ‘n’, then you’ll simply swap twice you’re done.
For the other cases, ie., i+1 is swappable with 1 or, your number is not swappable with ‘n’ or both you will swap your number with position 1 (either directly or through n), then swap it with position i+1 and bring back the number in position 1. The logic for k>=n/2 is also same, the positions that are not far enough from either ends can’t be used, and for every other position, there will always be one extreme position that it can move to.