Question

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 1: Dynamic Programming

We define $f[i]$ as the minimum number of operations to convert $arr1[0,..,i]$ into a strictly increasing array, and $arr1[i]$ is not replaced. Therefore, we set two sentinels $-\infty$ and $\infty$ at the beginning and end of $arr1$. The last number is definitely not replaced, so $f[n-1]$ is the answer. We initialize $f[0]=0$, and the rest $f[i]=\infty$.

Next, we sort the array $arr2$ and remove duplicates for easy binary search.

For $i=1,..,n-1$, we consider whether $arr1[i-1]$ is replaced. If $arr1[i-1] \lt arr1[i]$, then $f[i]$ can be transferred from $f[i-1]$, that is, $f[i] = f[i-1]$. Then, we consider the case where $arr[i-1]$ is replaced. Obviously, $arr[i-1]$ should be replaced with a number as large as possible and less than $arr[i]$. We perform a binary search in the array $arr2$ and find the first index $j$ that is greater than or equal to $arr[i]$. Then we enumerate the number of replacements in the range $k \in [1, min(i-1, j)]$. If $arr[i-k-1] \lt arr2[j-k]$, then $f[i]$ can be transferred from $f[i-k-1]$, that is, $f[i] = \min(f[i], f[i-k-1] + k)$.

Finally, if $f[n-1] \geq \infty$, it means that it cannot be converted into a strictly increasing array, return $-1$, otherwise return $f[n-1]$.

The time complexity is $(n \times (\log m + \min(m, n)))$, and the space complexity is $O(n)$. Here, $n$ is the length of $arr1$.

class Solution:
  def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
    arr2.sort()
    m = 0
    for x in arr2:
      if m == 0 or x != arr2[m - 1]:
        arr2[m] = x
        m += 1
    arr2 = arr2[:m]
    arr = [-inf] + arr1 + [inf]
    n = len(arr)
    f = [inf] * n
    f[0] = 0
    for i in range(1, n):
      if arr[i - 1] < arr[i]:
        f[i] = f[i - 1]
      j = bisect_left(arr2, arr[i])
      for k in range(1, min(i - 1, j) + 1):
        if arr[i - k - 1] < arr2[j - k]:
          f[i] = min(f[i], f[i - k - 1] + k)
    return -1 if f[n - 1] >= inf else f[n - 1]

class Solution {
  public int makeArrayIncreasing(int[] arr1, int[] arr2) {
    Arrays.sort(arr2);
    int m = 0;
    for (int x : arr2) {
      if (m == 0 || x != arr2[m - 1]) {
        arr2[m++] = x;
      }
    }
    final int inf = 1 << 30;
    int[] arr = new int[arr1.length + 2];
    arr[0] = -inf;
    arr[arr.length - 1] = inf;
    System.arraycopy(arr1, 0, arr, 1, arr1.length);
    int[] f = new int[arr.length];
    Arrays.fill(f, inf);
    f[0] = 0;
    for (int i = 1; i < arr.length; ++i) {
      if (arr[i - 1] < arr[i]) {
        f[i] = f[i - 1];
      }
      int j = search(arr2, arr[i], m);
      for (int k = 1; k <= Math.min(i - 1, j); ++k) {
        if (arr[i - k - 1] < arr2[j - k]) {
          f[i] = Math.min(f[i], f[i - k - 1] + k);
        }
      }
    }
    return f[arr.length - 1] >= inf ? -1 : f[arr.length - 1];
  }

  private int search(int[] nums, int x, int n) {
    int l = 0, r = n;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

class Solution {
public:
  int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
    sort(arr2.begin(), arr2.end());
    arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
    const int inf = 1 << 30;
    arr1.insert(arr1.begin(), -inf);
    arr1.push_back(inf);
    int n = arr1.size();
    vector<int> f(n, inf);
    f[0] = 0;
    for (int i = 1; i < n; ++i) {
      if (arr1[i - 1] < arr1[i]) {
        f[i] = f[i - 1];
      }
      int j = lower_bound(arr2.begin(), arr2.end(), arr1[i]) - arr2.begin();
      for (int k = 1; k <= min(i - 1, j); ++k) {
        if (arr1[i - k - 1] < arr2[j - k]) {
          f[i] = min(f[i], f[i - k - 1] + k);
        }
      }
    }
    return f[n - 1] >= inf ? -1 : f[n - 1];
  }
};

func makeArrayIncreasing(arr1 []int, arr2 []int) int {
  sort.Ints(arr2)
  m := 0
  for _, x := range arr2 {
    if m == 0 || x != arr2[m-1] {
      arr2[m] = x
      m++
    }
  }
  arr2 = arr2[:m]
  const inf = 1 << 30
  arr1 = append([]int{-inf}, arr1...)
  arr1 = append(arr1, inf)
  n := len(arr1)
  f := make([]int, n)
  for i := range f {
    f[i] = inf
  }
  f[0] = 0
  for i := 1; i < n; i++ {
    if arr1[i-1] < arr1[i] {
      f[i] = f[i-1]
    }
    j := sort.SearchInts(arr2, arr1[i])
    for k := 1; k <= min(i-1, j); k++ {
      if arr1[i-k-1] < arr2[j-k] {
        f[i] = min(f[i], f[i-k-1]+k)
      }
    }
  }
  if f[n-1] >= inf {
    return -1
  }
  return f[n-1]
}

function makeArrayIncreasing(arr1: number[], arr2: number[]): number {
  arr2.sort((a, b) => a - b);
  let m = 0;
  for (const x of arr2) {
    if (m === 0 || x !== arr2[m - 1]) {
      arr2[m++] = x;
    }
  }
  arr2 = arr2.slice(0, m);
  const inf = 1 << 30;
  arr1 = [-inf, ...arr1, inf];
  const n = arr1.length;
  const f: number[] = new Array(n).fill(inf);
  f[0] = 0;
  const search = (arr: number[], x: number): number => {
    let l = 0;
    let r = arr.length;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (arr[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };
  for (let i = 1; i < n; ++i) {
    if (arr1[i - 1] < arr1[i]) {
      f[i] = f[i - 1];
    }
    const j = search(arr2, arr1[i]);
    for (let k = 1; k <= Math.min(i - 1, j); ++k) {
      if (arr1[i - k - 1] < arr2[j - k]) {
        f[i] = Math.min(f[i], f[i - k - 1] + k);
      }
    }
  }
  return f[n - 1] >= inf ? -1 : f[n - 1];
}

public class Solution {
  public int MakeArrayIncreasing(int[] arr1, int[] arr2) {
    Array.Sort(arr2);
    int m = 0;
    foreach (int x in arr2) {
      if (m == 0 || x != arr2[m - 1]) {
        arr2[m++] = x;
      }
    }
    int inf = 1 << 30;
    int[] arr = new int[arr1.Length + 2];
    arr[0] = -inf;
    arr[arr.Length - 1] = inf;
    for (int i = 0; i < arr1.Length; ++i) {
      arr[i + 1] = arr1[i];
    }
    int[] f = new int[arr.Length];
    Array.Fill(f, inf);
    f[0] = 0;
    for (int i = 1; i < arr.Length; ++i) {
      if (arr[i - 1] < arr[i]) {
        f[i] = f[i - 1];
      }
      int j = search(arr2, arr[i], m);
      for (int k = 1; k <= Math.Min(i - 1, j); ++k) {
        if (arr[i - k - 1] < arr2[j - k]) {
          f[i] = Math.Min(f[i], f[i - k - 1] + k);
        }
      }
    }
    return f[arr.Length - 1] >= inf ? -1 : f[arr.Length - 1];
  }

  private int search(int[] nums, int x, int n) {
    int l = 0, r = n;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}