#1187

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Make Array Strictly Increasing

Determine the minimum operations to transform arr1 into a strictly increasing sequence using values from arr2 efficiently.

array binary search dynamic programming sorting

Problem Statement

You are given two integer arrays, arr1 and arr2. You can perform operations where you replace an element in arr1 with any element from arr2, aiming to make arr1 strictly increasing.

Return the minimum number of replacement operations required to achieve a strictly increasing arr1. If it is impossible to make arr1 strictly increasing through any sequence of replacements, return -1.

Examples

Example 1

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

Output: 1

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

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

You can't make arr1 strictly increasing.

Constraints

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

Solution Approach

Sort and Deduplicate arr2

Sort arr2 to allow efficient binary search for replacements and remove duplicates to prevent redundant operations that do not improve the strictly increasing property.

Dynamic Programming with State Tracking

Use a map or dictionary to track the minimum number of operations needed to reach each possible last value at every index in arr1. Transition states by either keeping the current element if it maintains strictly increasing order or replacing it using the next larger element from arr2 found via binary search.

Binary Search Optimization

For each element in arr1, use binary search on arr2 to find the smallest replacement that is larger than the previous element. Update the dynamic programming states with the minimum operations, ensuring efficiency within O(m * n * log n) time.

Complexity Analysis

Metric	Value
Time	O(m \cdot n \cdot\log n)
Space	O(n)

Time complexity is O(m * n * log n) because for each element in arr1 (length m) you may consider all elements in arr2 (length n) with a binary search. Space complexity is O(n) for storing the current dynamic programming states corresponding to arr2 values after deduplication.

What Interviewers Usually Probe

Checks understanding of dynamic programming state transitions for arrays.
Tests ability to optimize with binary search in sorted replacement arrays.
Evaluates handling of impossible cases and edge conditions in sequence transformations.

Common Pitfalls or Variants

Common pitfalls

Ignoring the need to sort and deduplicate arr2, leading to redundant checks.
Failing to properly track multiple states in dynamic programming, causing incorrect minimal operation counts.
Assuming a solution exists for all inputs, without checking impossible cases.

Follow-up variants

Find minimum replacements to make arr1 non-decreasing instead of strictly increasing.
Allow replacement elements from arr2 only at even indices of arr1.
Count the number of different strictly increasing sequences achievable with minimal replacements.

FAQ

What is the main approach for Make Array Strictly Increasing?

Use state transition dynamic programming combined with binary search on a sorted arr2 to minimize replacements.

Can arr1 be made strictly increasing without replacements?

Yes, if the original arr1 is already strictly increasing, zero operations are needed.

Why sort arr2 for this problem?

Sorting arr2 allows efficient binary search to find the next valid replacement for arr1 elements while maintaining strictly increasing order.

What if no strictly increasing sequence is possible?

Return -1, as some arr1 configurations cannot be fixed with any selection from arr2.

Does dynamic programming handle all edge cases?

Yes, by tracking all possible last values and minimal operations at each index, DP ensures correct results including impossible scenarios.

terminal

Solution

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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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]

Continue Practicing

#1235 maximum profit in job scheduling #792 number of matching subsequences #2008 maximum earnings from taxi