Find the number of remove-then-append operations needed to sort a given array

Question

This is an interview question. A swap means removing any element from the array and appending it to the back of the same array. Given an array of integers, find the minimum number of swaps needed to sort the array.

Is there a solution better than O(n^2)?

For example:

Input array: [3124].

The number of swaps: 2 ([3124] -> [1243] -> [1234]).

Answer 1

I think this problem can be solved in O(N) if you notice that an element in the array needs to be removed and appended if:

• There is a smaller element to the right or...
• There is a smaller element to his left that needs to be removed and appended.

Then it's just about identifying elements that will need to be removed and appended. Here is the code:

static int minMoves(int arr[], int n) {
    if (arr.length == 0) return 0;

    boolean[] willBeMoved = new boolean[n]; // keep track of elements to be removed and appended
    int min = arr[n - 1]; // keep track of the minimum

    for (int i = n - 1; i >= 0; i--) { // traverse the array from the right
        if (arr[i] < min) min = arr[i]; // found a new min
        else if (arr[i] > min) { // arr[i] has a smaller element to the right, so it will need to be moved at some point
            willBeMoved[i] = true;
        }
    }

    int minToBeMoved = -1; // keep track of the minimum element to be removed and appended
    int result = 0; // the answer

    for (int i = 0; i < n; i++) { // traverse the array from the left
        if (minToBeMoved == -1 && !willBeMoved[i]) continue; // find the first element to be moved
        if (minToBeMoved == -1) minToBeMoved = i;

        if (arr[i] > arr[minToBeMoved]) { // because a smaller value will be moved to the end, arr[i] will also have to be moved at some point
            willBeMoved[i] = true;
        } else if (arr[i] < arr[minToBeMoved] && willBeMoved[i]) { // keep track of the min value to be moved
            minToBeMoved = i;
        }

        if (willBeMoved[i]) result++; // increment
    }

    return result;
}

It uses O(N) space.

Answer 2

O(1) space and O(N) (~ 2*N) solution assuming min element is 1 and the array contains all numbers from 1 to N-1 without any duplicate value. where N is array length.

int minimumSwaps(int[] a) {
    int swaps = 0;
    int i = 0;
    while(i < a.length) {
        int position = a[i] - 1;
        if(position != i) {
            int temp = a[position];
            a[position] = a[i];
            a[i] = temp;
            swaps++;
        } else {
            i++;
        }
    }
    return swaps;
}

Answer 3

def minimumSwaps(arr):
    swaps = 0
    '''
    first sort the given array to determine the correct indexes 
    of its elements
    '''
    temp = sorted(arr)

    # compare unsorted array with the sorted one
    for i in range(len(arr)):
        '''
        if ith element in the given array is not at the correct index
        then swap it with the correct index, since we know the correct
        index because of sorting. 
        '''
        if arr[i] != temp[i]: 
          swaps += 1
          a = arr[i]
          arr[arr.index(temp[i])] = a
          arr[i] = temp[i]    
    return swaps

Answer 4

int temp = 0, swaps = 0;
        for (int i = 0; i < arr.length;) {
            if (arr[i] != i + 1){ 
            //  System.out.println("Swapping --"+arr[arr[i] - 1] +"  AND -- "+arr[i]);
                temp = arr[arr[i] - 1];
                arr[arr[i] - 1] = arr[i];
                arr[i] = temp;
                ++swaps;
            } else
                ++i;
                //  System.out.println("value at position -- "+ i +" is set to -- "+ arr[i]);
        }
        return swaps;

This is the most optimized answer i have found. It is so simple. You will probably understand in one look through the loop. Thanks to Darryl at hacker rank.

Answer 5

this is an O(n) solution which works for all inputs:

static int minimumSwaps(int[] arr) {
        int swap=0;
        boolean visited[]=new boolean[arr.length];

        for(int i=0;i<arr.length;i++){
            int j=i,cycle=0;

            while(!visited[j]){
                visited[j]=true;
                j=arr[j]-1;
                cycle++;
            }

            if(cycle!=0)
                swap+=cycle-1;
        }
        return swap;
    }
}

Answer 6

for(int count = 1; count<=length; count++)
{
    tempSwap=0; //it will count swaps per iteration
    for(int i=0; i<length-1; i++)
        if(a[i]>a[i+1])
        {
           swap(a[i],a[i+1]);
           tempSwap++;
        }
    if(tempSwap!=0) //check if array is already sorted!
        swap += tempSwap;
    else
        break;
}
System.out.println(swaps);

Answer 7

Here is the code in python for minimum number of swaps,

def find_cycles(array):
   cycles = []
   remaining = set(array)
   while remaining:
      j = i = remaining.pop()
      cycle = [i]
      while True:
         j = array[j]
         if j == i:
             break
         array.append(j)
         remaining.remove(j)
      cycles.append(cycle)
   return cycles

def minimum_swaps(seq):
    return sum(len(cycle) - 1 for cycle in find_cycles(seq))

Answer 8

Hear is my solution in c# to solve the minimum number of swaps required to short an array At at time we can swap only 2 elements(at any index position).

public class MinimumSwaps2
{
    public static void minimumSwapsMain(int[] arr)
    {

        Dictionary<int, int> dic = new Dictionary<int, int>();
        Dictionary<int, int> reverseDIc = new Dictionary<int, int>();
        int temp = 0;
        int indx = 0;
  //find the maximum number from the array
        int maxno = FindMaxNo(arr);

        if (maxno == arr.Length)
        {
            for (int i = 1; i <= arr.Length; i++)
            {
                dic[i] = arr[indx];
                reverseDIc.Add(arr[indx], i);
                indx++;
            }
        }
        else
        {
            for (int i = 1; i <= arr.Length; i++)
            {
                if (arr.Contains(i))
                {
                    dic[i] = arr[indx];
                    reverseDIc.Add(arr[indx], i);
                    indx++;
                }

            }
        }

        int counter = FindMinSwaps(dic, reverseDIc, maxno);


    }
    static int FindMaxNo(int[] arr)
    {
        int maxNO = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            if (maxNO < arr[i])
            {
                maxNO = arr[i];
            }
        }
        return maxNO;
    }
    static int FindMinSwaps(Dictionary<int, int> dic, Dictionary<int, int> reverseDIc, int maxno)
    {
        int counter = 0;
        int temp = 0;
        for (int i = 1; i <= maxno; i++)
        {
            if (dic.ContainsKey(i))
            {
                if (dic[i] != i)
                {
                    counter++;
                    var myKey1 = reverseDIc[i];
                    temp = dic[i];
                    dic[i] = dic[myKey1];
                    dic[myKey1] = temp;

                    reverseDIc[temp] = reverseDIc[i];
                    reverseDIc[i] = i;
                }
            }
        }
        return counter;
    }
}

Answer 9

Writing a very simple JavaScript program to sort an array and find number of swaps:

  function findSwaps(){

    let arr = [4, 3, 1, 2];
    let swap = 0
    var n = arr.length
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (arr[i] > arr[j]) {
                arr[i] = arr[i] + arr[j];
                arr[j] = arr[i] - arr[j];
                arr[i] = arr[i] - arr[j]
                swap = swap + 1
            }
        }
    }
    console.log(arr);
    console.log(swap)
  }

Answer 10

int numSwaps(int arr[], int length) {
bool sorted = false; 
int swaps = 0;
while(!sorted) {
    int inversions = 0;
    int t1pos,t2pos,t3pos,t4pos = 0;
    for (int i =  1;i < length; ++i)
    {
        if(arr[i] < arr[i-1]){
            if(inversions){
                tie(t3pos,t4pos) = make_tuple(i-1, i);
            }
            else tie(t1pos, t2pos) = make_tuple(i-1, i);
            inversions++;
        }
        if(inversions == 2)
            break;
    }
    if(!inversions){
        sorted = true;
    }
    else if(inversions == 1) {
        swaps++; 
        int temp = arr[t2pos];
        arr[t2pos] = arr[t1pos];
        arr[t1pos] = temp;
    }
    else{
        swaps++;
        if(arr[t4pos] < arr[t2pos]){
            int temp = arr[t1pos];
            arr[t1pos] = arr[t4pos];
            arr[t4pos] = temp;
        }
        else{
            int temp = arr[t2pos];
            arr[t2pos] = arr[t1pos];
            arr[t1pos] = temp;
        }
    }
}
return swaps;
}

This code returns the minimal number of swaps required to sort an array inplace.

For example, A[] = [7,3,4,1] By swapping 1 and 7, we get [1,3,4,7]. similarly B[] = [1,2,6,4,8,7,9]. We first swap 6 with 4, so, B[] -> [1,2,4,6,8,7,9]. Then 7 with 8. So -> [1,2,4,6,7,8,9]

The algorithm runs in O(number of pairs where value at index i < value at index i-1) ~ O(N) .

Answer 11

This can be done in O(n log n).

First find the minimum element in the array. Now, find the max element that occurs before this element. Call this max_left. You have to call swap()for all the elements before the min element of the array.

Now, find the longest increasing subsequence to the right of the min element, along with the constraint that you should skip elements whose values are greater than max_left. The required number of swaps is size(array) - size(LIS).

For example consider the array,

7 8 9 1 2 5 11 18

Minimum element in the array is 1. So we find the max before the minimum element.

7 8 9 | 1 2 5 11 18

max_left = 9

Now, find the LIS to the right of min with elements < 9 LIS = 1,2,5

No of swaps = 8 - 3 = 5

In cases where max element is null, ie., min is the first element, find the LIS of the array and required answer is size(array)-size(LIS)

For Example

2 5 4 3

max_left is null. LIS is 2 3

No of swaps = size(array) - size(LIS) = 4 - 2 = 2

Answer 12

@all , the accepted solution provided by @Itay karo and @NPE is totally wrong because it doesn't consider future ordering of swapped elements...

It fails for many testcases like:

3 1 2 5 4

correct output: 4

but their codes give output as 3...

explanation: 3 1 2 5 4--->1 2 5 4 3--->1 2 4 3 5--->1 2 3 5 4--->1 2 3 4 5

PS:i cann't comment there because of low reputation

Answer 13

This might work in O(nlogn) even if we don't assume array of consecutive values.
If we do - it can be done in O(n). One way of doing it is with O(n) space and O(nlogn) time.
Given array A sort it (O(nlogn)) into a second array B.
now... (arrays are indexed from 1)

swaps = 0
b = 1
for a = 1 to len(A)
  if A[a] == B[b]
    b = b + 1
  else
    swaps = swaps + 1

Answer 14

The problem boils down to finding the longest prefix of the sorted array that appears as a subsequence in the input array. This determines the elements that do not need to be sorted. The remaining elements will need to be deleted one by one, from the smallest to the largest, and appended at the back.

In your example, [3, 1, 2, 4], the already-sorted subsequence is [1, 2]. The optimal solution is to delete the remaning two elements, 3 and 4, and append them at the back. Thus the optimal solution is two "swaps".

Finding the subsequence can be done in O(n logn) time using O(n) extra memory. The following pseudo-code will do it (the code also happens to be valid Python):

l = [1, 2, 4, 3, 99, 98, 7]
s = sorted(l)
si = 0
for item in l:
  if item == s[si]:
    si += 1
print len(l) - si

If, as in your example, the array contains a permutation of integers from 1 to n, the problem can be solved in O(n) time using O(1) memory:

l = [1, 2, 3, 5, 4, 6]
s = 1
for item in l:
  if item == s:
    s += 1
print len(l) - s + 1

More generally, the second method can be used whenever we know the output array a priori and thus don't need to find it through sorting.

Answer 15

Observation: If an element is swapped to the back, its previous position does not matter. No element needs to be swapped more than once.

Observation: The last swap (if any) must move the largest element.

Observation: Before the swap, the array (excluding the last element) must be sorted (by former swaps, or initially)

Sorting algorithm, assuming the values are conecutive: find the longest sorted subsequence of consecutive (by value) elements starting at 1:

3 1 5 2 4

swap all higher elements in turn:

1 5 2 4 3

1 5 2 3 4

1 2 3 4 5

To find the number of swaps in O(n), find the length of the longest sorted subsequence of consecutive elements starting at 1:

• expected = 1
• for each element in sequence
  • if element == expected
    • expected += 1
• return expected-1

then the number of swaps = the length of the input - its longest sorted subsequence.

An alternative solution ( O(n^2) ) if the input is not a permutation of 1..n:

• swaps = 0
• loop
  • find the first instance of the largest element and detect if the array is sorted
  • if the array is sorted, return swaps.
  • else remove the found element from the array and increment swaps.

Yet another solution ( O(n log n) ), assuming unique elements:

• wrap each element in {oldPos, newPos, value}
• make a shallow copy of the array
• sort the array by value
• store the new position of each element
• run the algorithm for permutations on the newPos' in the (unsorted) copy

If you don't want to copy the input array, sort by oldPos before the last step instead.