Find the minimum number of ‘move-to-back’ required to sort an array

Problem

You are given an array of integers. Return the minimum number of ‘move-to-back’ required to sort the array in ascending order.

A ‘move-to-back’ is defined as removing an integer from it’s current position and pushing it to the end of the array

illustration of move-to-back

Sample Input: [1,4,2,5,3] | Expected Output: 2

1st move-to-back
2nd move-to-back

The solution to this problem is not immediately obvious. Although it might be tempting to take the approach of identifying the order in which elements need to be moved, it is important to note that the question is asking for the # of minimum of moves to complete this task, and not for the moves itself.

Approach

Find the number of elements in the correct relative position in relation to the sorted array.

N = 3

Observation

  • 1st, 3rd and 5th elements are already in relative sorted position.
  • 2nd and 4th elements are not in relative sorted order.

From the figure above, N = 3. The number of ‘move-to-back’ can now be calculated by subtracting N from the total length of the array. Here, we are ignoring the values of the elements which need to be moved, instead we are only interested in the number of elements which need to be moved.

# ‘moves-to-back’ = len(arr)-N = 5-3 = 2

Code

Once the approach has been understood, the implementation of the code is relatively straightforward.

def countMoveToBack(input): # input array
# sort given array
sorted_array = sorted(input)
sorted_idx = 0
# initialize counter
# loop through given array
for i in range(len(input)):
if input[i] == sorted_array[sorted_idx]:
sorted_idx += 1
min_moves = len(input) - sorted_idx
return min_moves

Time Complexity — O(nlog(n))

Space Complexity — O(n)

  • where n is the size of the input array

Variations

  • Calculate number of ‘move-to-front’
  • Sort in descending order

If you’ve found this walkthrough useful, would greatly appreciate a tasty clap. Let me know if you’ve found better solutions to this problem.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store