We first consider the case in which k < n/2. In this case we can obtain the sorted form of the original array.
Then consider the case in which k>=n/2. In this case the elements which will be at a distance of at most k from both the sides can not be swapped with any other integer and will thus remain in the same index as that in the original array. The remaining numbers can be sorted and placed in the remaining indices.
Can someone provide a more elaborate explanation to the solution proposed. Also can someone please provide the proof for the case when k<=n/2;
Thanks in advance
Make a graph with n vertices representing the indices of array with edges between all the indices whose values can be swapped. Now find the minimum value in the graph. Move the value to the minimum index by swapping values along the edges. After it has reached the minimum index, remove that vertex and all edges emanating from it. Repeat the process until all vertices are removed.
Following the above procedure, it can be observed that the array can be sorted for all the indices that lie in a connected component.
For k < n/2 all the indices form a connected component and hence the array can be sorted.
For k >= n/2 all elements except the elements at a distance of at most k from both the sides form a connected component and can be sorted.
Can anyone please give a formal proof why in the case of k >= n/2 the elements that are not fixed can be made into a sorted arrangement? Thanks in advance
