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.

  • $\begingroup$ What have you tried and where did you get stuck? Closely related questions: 1, 2. $\endgroup$
    – Raphael
    Sep 2, 2014 at 10:52

2 Answers 2


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.

  • $\begingroup$ 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. $\endgroup$
    – Matthew C
    Mar 18, 2020 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.