# What is the min # of moves to sort an array from 1 to n?

Problem: You are required to sort an array with numbers from 1 to n. You can do a "move", which means choosing one element and moving it to any place you want (insert to any place, not swap). Prove the minimum number of "moves" to sort the array is n - k, where k = the length of the longest increasing subsequence.

Ex: array is [1, 2, 5, 3, 4, 7, 6]

Longest increasing subsequence is [1, 2, 3, 4, 6], which is of length 5. Hence, the answer is 7 - 5 = 2 moves. You move numbers 5 and 7 to the correct spots.

I'd like a proof / intuition on why this has to be the minimum # of moves.

• What have you tried and where did you get stuck? Closely related questions: 1, 2. – Raphael Sep 2 '14 at 10:52

There is an invariant that each move can only increase the number in your longest increasing subsequence by at most 1.

If your initial array has $k$ values in its longest increasing subsequence, you need $n-k$ moves at least to get it sorted. This shows $n-k$ moves is necessary.

• This is really nice. It took me longer to think about why the invariant is true; for anyone like me I would suggest thinking about the move as 2 moves: a deletion and an insertion, and how the length of the LIS can be affected by either. – Matthew C Mar 18 at 4:30

Given answer is wrong because for example - let the given array is

    3 5 7 1 9 8


In the first step, 1 is removed and placed at first position, as a consequence the array becomes

    1 3 5 7 9 8


In the second step, 9 is removed and placed at the last position in the array, as a consequence the array becomes

    1 3 5 7 8 9


The array is now sorted. It took 2 steps to sort the array. You have to find out the minimum number of steps required to make the array sorted.

• In this case $k = 4$ (3,5,7,9) so $n-k=2$. I don’t see where the problem lies. – Yuval Filmus Mar 17 at 21:02