Minimum Swaps To Make Sequences Increasing

Description

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(javascript)

/*
 * @lc app=leetcode id=801 lang=javascript
 *
 * [801] Minimum Swaps To Make Sequences Increasing
 */

// @lc code=start
// /** 1: Top-down approach
//  * @param {number[]} A
//  * @param {number[]} B
//  * @return {number}
//  */
// const minSwap = function (A, B) {
//   const memo = {}
//   const aux = (index, prevSwapped) => {
//     const key = `${index}-${prevSwapped}`
//     if (memo[key] !== undefined) {
//       return memo[key]
//     }
//     if (index > A.length - 1) {
//       return 0
//     }
//     let min = Infinity
//     if (prevSwapped) {
//       if (A[index] > B[index - 1] && B[index] > A[index - 1]) {
//         min = Math.min(
//           min,
//           aux(index + 1, false),
//         )
//       }
//       if (B[index] > B[index - 1] && A[index] > A[index - 1]) {
//         min = Math.min(
//           min,
//           aux(index + 1, true) + 1,
//         )
//       }
//     } else {
//       if (B[index] > B[index - 1] && A[index] > A[index - 1]) {
//         min = Math.min(
//           min,
//           aux(index + 1, false),
//         )
//       }
//       if (A[index] > B[index - 1] && B[index] > A[index - 1]) {
//         min = Math.min(
//           min,
//           aux(index + 1, true) + 1,
//         )
//       }
//     }
//     memo[key] = min
//     return min
//   }
//   return Math.min(
//     aux(1, false),
//     aux(1, true) + 1,
//   )
// }

/** 1: Bottom-up approach
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */
const minSwap = function (A, B) {
  let memo = {
    true: 1,
    false: 0,
  }
  for (let index = 1; index < A.length; index++) {
    const current = {
      true: Infinity,
      false: Infinity,
    }
    if (A[index] > B[index - 1] && B[index] > A[index - 1]) {
      current.true = Math.min(
        current.true,
        memo.false + 1,
      )
      current.false = Math.min(
        current.false,
        memo.true,
      )
    }
    if (B[index] > B[index - 1] && A[index] > A[index - 1]) {
      current.true = Math.min(
        current.true,
        memo.true + 1,
      )
      current.false = Math.min(
        current.false,
        memo.false,
      )
    }

    memo = current
  }
  return Math.min(
    memo.false,
    memo.true,
  )
}
// @lc code=end