title: Sort an array by moving elements only to the beginning or the end
body: <p>I am trying to solve a difficult problem, and I'm afraid I've hit a roadblock - I'm out of ideas how to solve it. I thought maybe someone on here has stumbled upon something similar and, if not, I'm sure that those that like making algorithms will enjoy trying to find a solution:</p>
  
  <p>We are given an unsorted array. We are allowed to make one of two moves: take any element out of the array and move it either to the beginning or the end of the array. We are also given what the array should look like in the end. We are supposed to sort the array with the minimum number of steps.</p>
  
  <p>Example:</p>
  
  <pre><code> 5 1 4 3 2 - &gt; starting array
   3 1 2 5 4 - &gt; target array
  
   Steps: move 5 to the end 1 4 3 2 5 
   move 3 to the beginning  3 1 4 2 5
   move 4 to the end  3 1 2 5 4
  </code></pre>
  
  <p>The target array has been reached, the minimal number of steps is 3.</p>
  
  <p>Does anyone have any idea on how to solve this?</p>