801. Minimum Swaps To Make Sequences Increasing

801. Minimum Swaps To Make Sequences Increasing

Question

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

Solution

• Method 1: dp
  • we need to maintain 2 states: keep[i] and swap[i]. i means up to index i, two arrays are strictly increasing.
    • keep[i] means index i is not swapped.
    • swap[i] means index i is swapped.
  • Emample:
    • A: [x, x, x, 1 , 4]
    • B: [x, x, x, 2 , 3]
  • Two conditions:
    1. A[i - 1] < A[i] && B[i - 1] < B[i] Up to current index, two arrays have already met the requirement.
       • keep[i] = keep[i - 1] Nothing changed
       • swap[i] = swap[i - 1] + 1 both changed
         • A: [x, x, x, 2, 3]
         • B: [x, x, x, 1, 4]
    2. A[i - 1] < B[i] && B[i - 1] < A[i]
       • keep[i] = min(keep[i], swap[i - 1]) current i is not swapped, previous one swapped
         • A: [x, x, x, 2, 4]
         • B: [x, x, x, 1, 3]
       • swap[i] = min(swap[i], keep[i - 1] + 1) current is swapped, swap previous pair
         • A: [x, x, x, 2, 4]
         • B: [x, x, x, 1, 3]
  • Initialization
    • keep[0] = 0
    • swap[0] = 1

        class Solution {
        public int minSwap(int[] A, int[] B) {
        int len = A.length;
        if(len <= 1) return 0;
        int[] keep = new int[len];
        int[] swap = new int[len];
        Arrays.fill(keep, Integer.MAX_VALUE);
        Arrays.fill(swap, Integer.MAX_VALUE);
        keep[0] = 0; swap[0] = 0;
        for(int i = 1; i < len; i++){
            if(A[i - 1] < A[i] && B[i - 1] < B[i]){
                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]);
        }
        }
      

Reference

1. 花花酱 LeetCode 801. Minimum Swaps To Make Sequences Increasing - 刷题找工作 EP183