This is an interesting problem from LeetCode. It is one of the Medium level problems. It has been asked 9 times in Google and twice in the Amazon coding interview rounds.

So What Is The Problem?

We have two integer sequences A and B of the same non-zero length.

We are allowed to swap elements A[i] and B[i]. Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, A and B are both strictly increasing.

A sequence is strictly increasing if and only if
A[0] < A[1] <A[2]< … < A[A.length — 1]

Given A and B, we have to return the minimum number of swaps to make both sequences strictly increasing. It is guaranteed that the given input always makes it possible.

Example:
Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1
Explanation: 
Swap A[3] and B[3].  Then the sequences are:
A = [1, 3, 5, 7] and B = [1, 2, 3, 4]
which are both strictly increasing.

Note:
A, B are arrays with the same length, and that length will be in the range
[1, 1000].
A[i], B[i] are integer values in the range [0, 2000].

Coming To The Solution:

Approach Taken: Dynamic Programming

Let’s consider the following-

ni → naturally increasing sequence, a swap is therefore not done at position i.
si → represnts the number of swaps till position i considering a swap is done at position i.

1. Let variable n1 represent the cost of no swapping till the (i-1)th position in which case the elements are naturally increasing in order. That means n1 will be the number of elements that will be naturally increasing till the (i-1) position.
2. Let variable n2 represent the cost of naturally increasing till the (i)th position, so no swapping needs to be performed at the ith position.
3. Let variable s1 represent the cost when a swap is done at the (i-1)th position.
4. Let variable s2 represent the cost when a swap is done at the (i)th position.

Initial Values

n1=0 → n1 will naturally be 0 since the first element is going to have no larger element before it, so the number of swaps required would be 0

s1=1 → considering the first element is swapped so 1 swap till 1st position

Now there are basically 2 approaches that we need to consider for every loop iteration:

Case 1:

When adjacent elements of both arrays a[] and b[] are strictly increasing

if(a[i-1]<a[i] && b[i-1]<b[i])

n2=Math.min(n1,n2);

s2=Math.min(s2,s1+1); → Considering a swap is done at position i. A swap at (i)th position maybe needed for the (i+1)th position element to maintain the strictly increasing property.

Case 2:

When diagonal elements are also strictly increasing

if(a[i-1]<b[i] && b[i-1]<a[i])

Note : If the diagonal elements are strictly increasing, the adjacent elements of both arrays may or may not be strictly increasing.

If both case 1 and case 2 hold true.. i.e, if the adjacent elements are strictly increasing and the diagonal elements are also strictly increasing, then the values of n2 and s2 need to be floored.

n2=Math.min(n2,s1); → Considering we are not swapping, n2 will be the minimum between the natural n2 till (i)th position and number of swaps s2 done till (i-1)th position.This comes into effect for cases where adjacent elements are not strictly increasing but diagonal elements are strictly increasing so swapping needs to be done.

s2=Math.min(s2,n1+1) → Minimum of (swaps done till the ith position) and the (count of natural till the (i-1)th position + 1 swap done for the ith position). (n1+1) is taken as the second parameter since the elements are strictly increasing even for diagonal elements, so even if we swap the (i)th element, the cost would end up being (n1+1).

Before the loop goes for the iteration considering the next pair of elements,
n1=n2;
s1=s2;

Finally,

return Math.min(n1,s1);

The minimum of natural and the number of swaps is returned.

Below is the function coded in Java for your reference :

public int minSwap(int[] a, int[] b) {
int i;int n1,n2,s1,s2;
//n1 represents no swapping till the (i-1)th position in which case the elements are naturally increasing in order. n2 represents no swapping at the ith position

//s1 represents swap is done at the (i-1)th pos and
//s2 represnts a swap is performed at the ith position

n1=0; //n1 will naturally be 0 since the first element is going to have no larger element before it, so the number of swaps required would be 0
s1=1; //considering the first element is swapped

for(i=1;i<a.length;i++)
{
n2=Integer.MAX_VALUE;
s2=Integer.MAX_VALUE;

//the case where adjacent elements of both the arrays are strictly increasing
if(a[i-1]<a[i] && b[i-1]<b[i])
{
n2=Math.min(n1,n2);
s2=Math.min(s2,s1+1); //still considering a swap is done since a swap at ith //position maybe needed for the (i+1)th position //element to maintain the strictly increasing property
}

//the case where diagonal elements are also strictly increasing in which case the values need to be floored. If the diagonal elements are strictly increasing, //the adjacent elements of both arrays may or may not be
//strictly increasing which is why this condition is there
if(a[i-1]<b[i] && b[i-1]<a[i])
{
n2=Math.min(n2,s1); //for cases where adjacent elements are not strictly increasing so swapping needs to be done
s2=Math.min(s2,n1+1);//Minimum of (swaps till the ith position) and the (count of natural till the (i-1)th position + 1 swap for the ith position)
}
n1=n2;
s1=s2;
}
//minimum of natural and the number of swaps is returned
return Math.min(n1,s1);
}

Function that calculates minimum numbers of swaps to make sequences increasing