1187. Make Array Strictly Increasing

Description

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

 

Example 1:

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Example 2:

Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].

Example 3:

Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.

 

Constraints:

• 1 <= arr1.length, arr2.length <= 2000
• 0 <= arr1[i], arr2[i] <= 10^9

 

 

Solutions

Solution: Dynamic Programming + Binary Search

• Time complexity: O(arr1.length*nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @return {number}
 */
const makeArrayIncreasing = function (arr1, arr2) {
  const n = arr2.length;
  let dp = new Map([[-1, 0]]);

  arr2.sort((a, b) => a - b);

  const getAssignIndex = target => {
    let left = 0;
    let right = n;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);

      arr2[mid] > target ? (right = mid) : (left = mid + 1);
    }
    return left;
  };

  for (const num of arr1) {
    const nextDp = new Map();

    for (const [value, times] of dp) {
      if (num > value) {
        const numTimes = nextDp.get(num) ?? Number.MAX_SAFE_INTEGER;

        nextDp.set(num, Math.min(numTimes, times));
      }
      const index = getAssignIndex(value);

      if (index === n) continue;
      const assignNum = arr2[index];
      const assignNumTimes = nextDp.get(assignNum) ?? Number.MAX_SAFE_INTEGER;

      nextDp.set(assignNum, Math.min(assignNumTimes, times + 1));
    }
    if (!nextDp.size) return -1;
    dp = nextDp;
  }
  return Math.min(...dp.values());
};