Minimal calls to subArrayLeftShift method for sorting array (interview question)

Question

Suppose you have a method subArrayLeftShift(a,i) which shifts left the sub array a[i,...,n-1] when n is the array length. That means that the elements a[i+1],...,a[n-1] are moving one place to the left, and the original a[i] will become the last one.

More formally, here is the function implementation:

public static void subArrayLeftShift(int[] a, int i){
  if (a.length == 0) return;

  int last = a.length - 1;
  int insertToLast = a[i];
  for (; i < last; i++){
      a[i] = a[i + 1];
  }
  a[last] = insertToLast;
}

Now for the question: implement a function that receives an unsorted array, and returns the minimal number of calls to subArrayLeftShift for sorting the array.

In the interview I couldnt find the way to do it. I succeed to find the minimal number of calls for every example I wrote for intuition, but couldn't find a way for generalizing it.

Do you know how to solve it?

Answer 1

I propose the following algorithm to solve the problem:

• Find the minimum number in the array that is not sorted ( has a smaller number on the right in the array). Let this number be x.
• Count how many numbers in the array are greater than the previously found number x. Let this number be y.

Since for each call to the function, the unsorted number will end up at the last position, the optimum strategy is to call the function for each unsorted number in increasing order. Using what was found previously we start with x. We continue with the next unsorted number bigger than x, because in this way, it will end up on the right of x, hence it will be sorted. Continue in the same fashion. How much? How many bigger number than x we have? Well, that's y. So as a total, the number of calls to the function is 1 + y.