Algorithm

Problem Name: 1187. Make Array Strictly Increasing

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`

Code Examples

#1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const makeArrayIncreasing = function(arr1, arr2) {
arr2.sort((a, b) => a - b)
let arr3 = [arr2[0]]
for (let i = 1; i  <  arr2.length; i++) {
if (arr2[i] > arr2[i - 1]) {
arr3.push(arr2[i])
}
}
arr2 = arr3
let n = arr1.length
let indexMap = new Array(n * 2 + 2)
for (let i = 0; i  <  n; i++) {
let ai = arr1[i]
let li = findLarger(arr2, ai)
indexMap[i * 2] = li
indexMap[i * 2 + 1] = arr2[li - 1] === ai ? li - 2 : li - 1
}
indexMap[n * 2] = arr2.length
indexMap[n * 2 + 1] = arr2.length - 1
let dp = new Array(n + 1)
let MaxNum = 1000000000 + 1
dp[0] = 0
for (let i = 1; i  <  n + 1; i++) {
let min = i
let ai = i === n ? MaxNum : arr1[i]
for (let j = 0; j  <  i; j++) {
if (dp[j] == -1 || ai <= arr1[j]) {
continue
}
if (indexMap[i * 2 + 1] - indexMap[j * 2] + 1 < i - j - 1) continue
min = Math.min(min, dp[j] + i - j - 1)
}
if (min === i) {
if (indexMap[i * 2 + 1] + 1 < i) {
min = -1
}
}
dp[i] = min
}
return dp[n]
}
const findLarger = function(arr, a) {
if (a > arr[arr.length - 1]) return arr.length
let l = 0
let r = arr.length - 1
while (l < r) {
let mid = (l + r) >> 1
if (arr[mid] <= a) {
l = mid + 1
} else {
r = mid
}
}
return l
}
``````
Copy The Code &

Input

cmd
arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]

Output

cmd
1

#2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
dp = {-1:0}
arr2.sort()
for i in arr1:
tmp = collections.defaultdict(lambda: float('inf'))
for key in dp:
if i > key:
tmp[i] = min(tmp[i],dp[key])
loc = bisect.bisect_right(arr2,key)
if loc < len(arr2):
tmp[arr2[loc]] = min(tmp[arr2[loc]],dp[key]+1)
dp = tmp
if dp:
return min(dp.values())
return -1
.``````
Copy The Code &

Input

cmd
arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]

Output

cmd
1