Problem Explanation:

We are provided with two integer sequences with the same non-zero length and we need to make both the sequences strictly increasing by a certain number of swaps between the corresponding elements of the two sequences.

A sequence is strictly increasing if each element is greater than the one before it.

Our task is to find the minimum number of swaps we need to make to achieve this. It is guaranteed that such a scenario is always possible with the provided input.

Example:

Let's take the example of A = [1,3,5,4] and B = [1,2,3,7].

The sequences are not strictly increasing because in the sequence~A, the last element 4 is smaller than the second last element 5.

To make both the sequences strictly increasing, we can swap the last elements of both A and B.

After the swap, A = [1, 3, 5, 7] and B = [1, 2, 3, 4]

Both sequences are now strictly increasing and we had to perform only 1 swap. So, the output for this input should be 1.

Approach:

The problem can be solved by using dynamic programming.

There are two arrays keepAt and swapAt, representing the minimum number of swaps found so far if we keep the elements at position i in both arrays as it is and the minimum number of swaps if we swap the elements at position i respectively.

For every i in nums1 and nums2, if nums1[i] > nums1[i - 1] and nums2[i] > nums2[i - 1] that means both them are in increasing sequence till i, thus you have two options:

• You swap both i and i-1
• You don't swap either

This logic is covered in the first if block where we are just carrying forward the swap and not-swap counts till the last encountered element.

But if nums1[i] > nums2[i - 1] and nums2[i] > nums1[i - 1], that means the elements are not strictly increasing and we have two options:

• You swap the current one but not the last one.
• You swap the last one but not the current one.

So basically at every index, we need to make a decision whether to swap or not and also decide about the last index whether it was swapped or not to maintain the strictly increasing sequence.

Finally, we return the minimum of the last elements of the keepAt and the swapAt arrays, which will represent the minimum number of swaps needed to make the two sequences strictly increasing.

Solutions:

Python

1
2python
3class Solution:
4    def minSwap(self, nums1, nums2):
5        n = len(nums1)
6        keepAt = [0] + [float('inf')]*n
7        swapAt = [1] + [float('inf')]*n
8        for i in range(1, n):
9            if nums1[i] > nums1[i-1] and nums2[i] > nums2[i-1]:
10                keepAt[i+1] = keepAt[i]
11                swapAt[i+1] = swapAt[i] + 1
12            if nums1[i] > nums2[i-1] and nums2[i] > nums1[i-1]:
13                keepAt[i+1] = min(keepAt[i+1], swapAt[i])
14                swapAt[i+1] = min(swapAt[i+1], keepAt[i] + 1)
15        return min(keepAt[-1], swapAt[-1])

JAVA

1
2java
3class Solution {
4    public int minSwap(int[] A, int[] B) {
5        int n = A.length;
6        int[] keep = new int[n];
7        int[] swap = new int[n];
8        Arrays.fill(keep, Integer.MAX_VALUE);
9        Arrays.fill(swap, Integer.MAX_VALUE);
10        keep[0] = 0;
11        swap[0] = 1;
12        for (int i = 1; i < n; i++) {
13            if (A[i] > A[i-1] && B[i] > B[i-1]) {
14                keep[i] = keep[i-1];
15                swap[i] = swap[i-1] + 1;
16            }
17            if (A[i] > B[i-1] && B[i] > A[i-1]) {
18                keep[i] = Math.min(keep[i], swap[i-1]);
19                swap[i] = Math.min(swap[i], keep[i-1] + 1);
20            }
21        }
22        return Math.min(keep[n-1], swap[n-1]);
23    }
24}

JavaScript

1
2javascript
3var minSwap = function(A, B) {
4    var N = A.length;
5    var swap = new Array(N).fill(Number.MAX_VALUE);
6    var keep = new Array(N).fill(Number.MAX_VALUE);
7    swap[0] = 1;
8    keep[0] = 0;
9    for (var i = 1; i < N; ++i) {
10        if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
11            keep[i] = keep[i - 1];
12            swap[i] = swap[i - 1] + 1;
13        }
14        if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
15            keep[i] = Math.min(keep[i], swap[i - 1]);
16            swap[i] = Math.min(swap[i], keep[i - 1] + 1);
17        }
18    }
19    return Math.min(keep[N-1], swap[N-1]);
20};

C++

1
2C++
3class Solution 
4{
5public:
6    int minSwap(vector<int>& A, vector<int>& B) 
7    {
8        int n = A.size();
9        vector<int> keep(n, INT_MAX);
10        vector<int> swap(n, INT_MAX);
11        keep[0] = 0, swap[0] = 1;
12        for(int i=1; i<n; i++)
13        {
14            if(A[i] > A[i-1] && B[i] > B[i-1])
15            {
16                keep[i] = keep[i-1];
17                swap[i] = swap[i-1] + 1;
18            }
19            
20            if(A[i] > B[i-1] && B[i] > A[i-1])
21            {
22                keep[i] = min(keep[i], swap[i-1]);
23                swap[i] = min(swap[i], keep[i-1] + 1);
24            }
25        }
26        return min(keep[n-1], swap[n-1]);
27    }
28};

C#

1
2C#
3public class Solution {
4    public int MinSwap(int[] A, int[] B) {
5        int n = A.Length;
6        int[] keep = new int[n];
7        int[] swap = new int[n];
8        Array.Fill(keep, Int32.MaxValue);
9        Array.Fill(swap, Int32.MaxValue);
10        keep[0] = 0;
11        swap[0] = 1;
12        for (int i = 1; i < n; i++) {
13            if (A[i] > A[i-1] && B[i] > B[i-1]) {
14                keep[i] = keep[i-1];
15                swap[i] = swap[i-1] + 1;
16            }
17            if (A[i] > B[i-1] && B[i] > A[i-1]) {
18                keep[i] = Math.Min(keep[i], swap[i-1]);
19                swap[i] = Math.Min(swap[i], keep[i-1] + 1);
20            }
21        }
22        return Math.Min(keep[n-1], swap[n-1]);
23    }
24}

Using this approach, we solve the problem by scanning the sequences from left to right, considering different alternatives at each pair of numbers in the input arrays.

In other words, at each step we'll calculate two values keepAt[i] and swapAt[i]. keepAt[i] represents the minimal number of swaps in order to make arrays A[0, ..., i] and B[0, ..., i] increasing by not swapping the i-th elements. Similarly, swapAt[i] represents the minimal number of swaps in order to make arrays A[0, ..., i] and B[0, ..., i] increasing by swapping the i-th elements.

In the end of our scan, we'll just return the minimum between swapAt[n-1] and keepAt[n-1] where n is the length of our input arrays.

While the overall approach and implementation of our algorithm among these languages are quite similar, the syntax differences provide us some unique aspects in each one.

Python, for instance, is quite essential in this problem due to its simplicity in declaring and initializing list with prepopulated values. Python makes this problem look very simpler as compared to other languages.

Java and C# are similar regarding their verbosity which may be a good thing when we want to write more explicit and perhaps better documented code. This can be particularly useful for more complex problems where we need to do multiple things at each step of our dynamic programming table filling.

Javascript on the other hand, requires some additional steps for list manipulation and initialization though it gets the job done efficiently.

Overall each language has its strength and depending on the coder's proficiency in a certain language, the problem can be implemented in any of these languages with a high degree of efficiency and readability.