# Minimum Swaps To Make Sequences Increasing

# A LeetCode Medium Level Problem

Spreeha Dutta

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:1Explanation:

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.

- 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. - 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. - Let variable
**s1**represent the cost when a swap is done at the (i-1)th position. - 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

Upvote

Spreeha Dutta

Navigating my way through life's beautiful stories!

Related Articles