Leetcode 801. Minimum Swaps To Make Sequences Increasing

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, 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].

A Wrong Solution (Greedy):

The first idea is to use greedy algorithm. Since we know that there must be at least one solution, we just scan the array A. If we found the sequence is not strictlly increasing, we just swap with B. Then we also need to scan the array B again since B may not be increasing. 

Code (Java):

class Solution {
    public int minSwap(int[] A, int[] B) {
        int numOfSwaps = 0;
        
        // First scan of A
        //
        for (int i = 1; i < A.length; i++)
        {
            if (A[i] <= A[i - 1])
            {
                swap(A, B, i);
                numOfSwaps++;
            }
        }
        
        // Second scan of B to make sure we did not miss anything
        //
        for (int i = 1; i < B.length; i++)
        {
            if (B[i] <= B[i - 1])
            {
                swap(A, B, i);
                numOfSwaps++;
            }
        }
        
        return numOfSwaps;
    }
    
    private void swap(int[] A, int[] B, int index)
    {
        int temp = A[index];
        A[index] = B[index];
        B[index] = temp;
    }
}

Analysis:
So why the solution is wrong? One example is

Input:[0,4,4,5,9] [0,1,6,8,10]

Output:2

Expected:1

So we only need to swap A[1] with B[1]. That's the miminum number of swaps.
It tells us greedy algorithm does not work most of the time.


Correct Solution:
This problem is a classic sackpack problem. For each pair of A[i] and B[i], we can choose to swap or not. So we define two dp arrays, keep[i] means if we don't swap A[i] and B[i], what's the min number of swaps. swap[i] is the min number of swaps if we swap A[i] and B[i].

Since the problem guarantees that there is a valid solution. We only need to consider two cases:

1. A[i] > A[i -1] && B[i] > B[i - 1],
if we choose to keep, we should keep the previous i - 1 elements. So keep[i] = keep[i - 1]
If we choose to swap, in order to maintain the sequencing order, we must swap the previous i - 1 th element. So swap[i] = swap[i - 1] + 1;

2. A[i] > B[i - 1] && B[i] > A[i - 1]
If we choose to keep, keep[i] = Math.min(keep[i], swap[i - 1])
If we choose to swap, swap[i] = Math.min(swap[i], keep[i - 1] + 1)

3. For other cases such as A[i] < B[i - 1] we don't need to consider since we gurantee there will be a solution.

Code (Java):

class Solution {
    public int minSwap(int[] A, int[] B) {
        int len = A.length;
        int[] keep = new int[len];
        int[] swap = new int[len];
        
        // Init for max
        //
        for (int i = 0; i < len; i++)
        {
            keep[i] = Integer.MAX_VALUE;
            swap[i] = Integer.MAX_VALUE;
        }
        
        keep[0] = 0;
        swap[0] = 1;
        
        for (int i = 1; i < len; i++)
        {
            if (A[i] > A[i - 1] && B[i] > B[i - 1])
            {
                keep[i] = keep[i - 1];
                swap[i] = swap[i - 1] + 1;
            }
            
            if (A[i] > B[i - 1] && B[i] > A[i - 1])
            {
                keep[i] = Math.min(keep[i], swap[i - 1]);
                swap[i] = Math.min(swap[i], keep[i - 1] + 1);
            }
        }
        
        return Math.min(keep[len - 1], swap[len - 1]);
    }
}