Minimum swaps to relative sort two arrays

Question

Given two arrays arr1 and arr2, we have to find the minimum swaps to relatively sort the two arrays into strictly increasing order. If relative sort is not possible, then -1 is returned.

The relative sort is defined as exchanging the same index element of arr1 and arr2.

That is, steps for relative sort:

swap(arr1[i], arr2[i])

And strictly increasing order is defined as:

arr[i+1]>arr[i] for all i

Example:

arr1={1,4,4,9} 
arr2={2,3,5,10}

Then minimum swaps is 1, as interchanging arr1[2] and arr2[2], will make both the arrays strictly increasing. I solved the question using recursion. If arr[i]>arr[i+1], we can either swap elements at index i or elements at index i+1, and then call the function for index i+1. I tried to find the minimum of the two values and returned it. This procedure was followed for each index of i.

int f(int N, int *arr1, int *arr2, int i){
    if(i == N-1)
        return 0;
     if(arr1[i]>=arr1[i+1] && arr2[i]>=arr2[i+1])return -1;
    if(arr1[i]>=arr1[i+1] || arr2[i]>=arr2[i+1]){
        int m, n;
        swap(arr1[i], arr2[i]);
        m = f(N, arr1, arr2, i+1);
        swap(arr1[i], arr2[i]);
        swap(arr1[i+1, arr2[i+1]);
        n = f(N, arr1, arr2, i+1);
        if(m == -1 && n==-1)return -1;
        if(m==-1)return n;
        if(n==-1)return m;
        return min(m, n);
    }
    return f(N, arr1, arr2, i+1);
 }

int minSwaps(int N, int *arr1, int *arr2){
    return f(N, arr1, arr2, 0);
}

As this was a question I faced in an online coding test, I got the basic test cases passed, but I am still not sure whether this method would work for all test cases.

Also, I wonder if this question can be solved using dynamic programming. If yes, what state should be stored in table? And what should be the approach?

Answer 1

int minSwap(vector<int>& a, vector<int>& b){
    int inf = (int)(1e9);
    int n=a.size();
    int dp[n][2];
    dp[0][0]=0;
    dp[0][1]=1;
    for(int i=1;i<n;i++)
        dp[i][0]=dp[i][1]=inf;
    for(int i=1;i<n;i++){
        if(a[i-1]<a[i]&&b[i-1]<b[i]){
            dp[i][0]=dp[i-1][0];
            dp[i][1]=dp[i-1][1]+1;
        }
        if(a[i-1]<b[i]&&b[i-1]<a[i]){
            dp[i][0]=min(dp[i][0],dp[i-1][1]);
            dp[i][1]=min(dp[i][1],dp[i-1][0]+1);
        }
    }
    return min(dp[n-1][0],dp[n-1][1]);
}

Answer 2

Your solution is exponential in the size of array. As you have noticed in your question, the solution can be obtained using dynamic programming.

First, let's define a helper function that checks whether after we swap i-th and/or i + 1-st element we obtain a locally valid solution. What I mean by locally valid is only considering these four numbers.

def isValid(i, preSwap, postSwap):
  val lx = if (preSwap) y(i) else x(i)
  val rx = if (postSwap) y(i + 1) else x(i + 1)
  val ly = if (preSwap) x(i) else y(i)
  val ry = if (postSwap) x(i + 1) else y(i + 1)
  // x(i) < x(i + 1) && y(i) < y(i + 1)
  lx < rx && ly < ry

Now, we will simply loop backwards the array. Our dynamic programming memory would be constant - we have to remember just two integers. Let's consider i-th iteration for i = x.length - 2 downto 0.

• what is the optimal number of swaps so that indicies i + 1 upto x.length - 1 are sorted increasingly and x(i) and y(i) are not swapped,
• what is the optimal number of swaps so that indicies i + 1 upto x.length - 1 are sorted increasingly and x(i) and y(i) are swapped.

For a list of length 1 we obtain a tuple (prevNoSwap, prevSwap) = (0, 1). Our loop step would consider four cases:

• we don't swap at i and we don't swap at i + 1; optimal: prevNoSwap,
• we swap at i and we don't swap at i + 1; optimal: prevNoSwap + 1,
• we don't swap at i and we swap at i + 1; optimal: prevSwap,
• we swap at i and we don't swap at i + 1; optimal: prevSwap + 1.

If given case creates valid solution we would consider it as a possible number of steps. We group them by swapping / not swapping at i and take the minimum. We assume that any of these elements might become Infinity if the solution cannot be found in specific case.

After the loop we pick a minimum of two tuple values. Here's the rest of the pseudocode:

state = (0, 1)
for i in x.length - 2 downto 0
  noPreSwap, withPreSwap = [#INFINITY], [#INFINITY]

  if (isValid(i, preSwap = false, postSwap = false)) noPreSwap += state.left
  if (isValid(i, preSwap = false, postSwap = true)) noPreSwap += state.right
  if (isValid(i, preSwap = true, postSwap = true)) withPreSwap += state.right + 1
  if (isValid(i, preSwap = true, postSwap = false)) withPreSwap += state.right

  state = (noPreSwap.min(), withPreSwap.min())
return if state.min().isInfinity() -1 else state.min()