Mock interview Nov. 15, 2020 10:00 PM as an interviewer

801MinimumSwapsToMakeSequencesIncreasing.js

const _ = require('lodash');

function sayHello() {
  console.log('Hello, World');
}

_.times(5, sayHello);


/* 
Your previous Plain Text content is preserved below:

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



Case 1:
A = [7,1,2]
B = [0,5,7]


backtracking

A = [1,3,5,4], 
B = [1,2,3,7]
     1 3 5
     1 2 3
       2 3
       3 5
 
 A = [1, 3, 10, 5, 7]
B = [1, 2, 4, 12, 14]
 
A = [1, 3, 8]
and
B = [2, 7, 4]

dp  _          _        _ 
  [1,2,0]    [3,7,0]    [8,4,1]
  [2,1,1]    [7,3,1]    [4,8,1]
i  0           1        2

return min(dp[lastindex][0][2])
       
dp[i]  [A[i], B[i], minSwap]
       [B[i], A[i], minSwap]
       
       At index i,
        no swap: [A[i], B[i]]
          find minSwap in dp[i-1] seq in increasing order
          if possible, push dp[i] an element [A[i], B[i], minSwap+1]
        swap: [B[i], A[i]]
        

 */

//Time : O(n) Space: O(n)
let minSwap = (A, B) => {
  let N = A.length;
  let dp = Array(N);
  dp[0] = [[A[0], B[0], 0], [B[0], A[0], 1]];
  
  for(let i = 1; i<N; i++){
    dp[i] = [];
    let noSwap = [A[i], B[i], +Infinity];
    
    for(let [prevA, prevB, prevMinSwap] of dp[i-1]){
      if(noSwap[0] > prevA && noSwap[1] > prevB){
          noSwap[2] = Math.min(noSwap[2], prevMinSwap);
      }
    }
    
    dp[i].push(noSwap);
    
    let swap = [B[i], A[i], +Infinity];
    
    for(let [prevA, prevB, prevMinSwap] of dp[i-1]){
      if(swap[0] > prevA && swap[1] > prevB){ // statement ? 
          swap[2] = Math.min(swap[2], prevMinSwap + 1);  // swap B[i] and
      }
    }
    
    dp[i].push(swap);
  }
  
  return Math.min(dp[N-1][0][2], dp[N-1][1][2]);
}


let A = [1, 3, 8];
let B = [2, 7, 4];
console.log("min swap: ", minSwap(A, B));

A = [1,3,5,4] 
B = [1,2,3,7]
console.log("min swap: ", minSwap(A, B));

 A = [1, 3, 10, 5, 7]
B = [1, 2, 4, 12, 14]
console.log("min swap: ", minSwap(A, B));