{x}
blog image

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

 

Solution: Make Array Strictly Increasing

This problem asks to find the minimum number of operations needed to make arr1 strictly increasing by replacing elements of arr1 with elements from arr2. The solution uses dynamic programming.

Approach

  1. Preprocessing arr2: Sort arr2 and remove duplicate elements. This optimization significantly speeds up the binary search in the later steps.

  2. Dynamic Programming: We use a DP array f where f[i] represents the minimum number of operations needed to make the subarray arr1[0...i] strictly increasing. We add sentinel values (-∞ and ∞) to the beginning and end of arr1 to handle base cases.

  3. Transition: For each element arr1[i], we consider two possibilities:

    • No replacement: If arr1[i] is greater than arr1[i-1], then we can keep arr1[i] without any additional operation. In this case, f[i] = f[i-1].
    • Replacement: If arr1[i] is not greater than arr1[i-1], we need to replace arr1[i] with a suitable element from arr2. We find the smallest element in arr2 that is greater than arr1[i-1] using binary search. Then, we consider replacing previous elements as well to minimize operations. We iterate through possible replacements of previous elements(from i-1 to max(0, i-m)), where m is the number of elements in arr2 that are greater than arr1[i-1]. For each possible number of replacements k, if the condition arr1[i-k-1] < arr2[j-k] holds (where j is the index of the found element in arr2), we update f[i] to be the minimum of f[i] and f[i-k-1]+k.

  4. Result: f[n-1] (where n is the length of arr1) will contain the minimum number of operations to make the entire array strictly increasing. If f[n-1] is still infinity, it means it's impossible to make arr1 strictly increasing, so we return -1.

Time and Space Complexity

  • Time Complexity: O(n * (log m + min(n, m))), where n is the length of arr1 and m is the length of arr2 after removing duplicates. The dominant factor is the nested loop that iterates through possible replacements. The binary search adds a log m factor.
  • Space Complexity: O(n) to store the DP array f.

Code (Python)

import bisect
 
class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2.sort()
        arr2 = list(dict.fromkeys(arr2)) #remove duplicates
        arr = [-float('inf')] + arr1 + [float('inf')]
        n = len(arr)
        dp = [float('inf')] * n
        dp[0] = 0
        for i in range(1, n):
            if arr[i - 1] < arr[i]:
                dp[i] = dp[i - 1]
            j = bisect.bisect_left(arr2, arr[i])
            for k in range(1, min(i, j) + 1):
                if arr[i - k - 1] < arr2[j - k]:
                    dp[i] = min(dp[i], dp[i - k - 1] + k)
        return dp[n - 1] if dp[n - 1] != float('inf') else -1

The code in other languages (Java, C++, Go, TypeScript, C#) follows the same algorithm and logic, differing only in syntax and standard library functions. The core DP approach and complexity analysis remain the same across all implementations.