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: Replace5with2, thenarr1 = [1, 2, 3, 6, 7].
Example 2:
Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1] Output: 2 Explanation: Replace5with3and then replace3with4.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 <= 20000 <= 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
}
Input
arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output
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
.Input
arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output
1