LeetCode 1187 - Make Array Strictly Increasing

The problem is asking us to transform the array arr1 into a strictly increasing array using the minimum number of operations. Each operation allows replacing an element of arr1 with an element from arr2.

leetcodehardarraybinary-searchdynamic-programmingsorting

LeetCode Problem 1187

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Dynamic Programming, Sorting

Solution

Problem Understanding

The problem is asking us to transform the array arr1 into a strictly increasing array using the minimum number of operations. Each operation allows replacing an element of arr1 with an element from arr2. The final array must satisfy the strictly increasing condition, meaning each element is strictly greater than the previous one.

The input consists of two arrays: arr1 of length n and arr2 of length m. The output is an integer representing the minimum number of replacement operations required. If it is impossible to make arr1 strictly increasing, we return -1.

The constraints indicate that arr1 and arr2 can each contain up to 2000 elements, and each element can be as large as $10^9$. This means a naive brute-force solution that tries all combinations would be computationally infeasible, as the number of combinations grows exponentially with the length of the array.

Edge cases include arrays that are already strictly increasing, arrays where no replacements can help, arrays with duplicate elements in arr2, and scenarios where all elements are equal.

Approaches

Brute-Force Approach

The brute-force solution considers every possible sequence of replacements. At each position in arr1, we have the choice to either keep the current element or replace it with any element from arr2. This leads to a tree of possibilities, where each node represents the current state of the array and the number of operations performed. We would recursively explore all paths and pick the one that results in a strictly increasing array with the fewest operations. While correct, this approach is infeasible for large inputs because its time complexity is exponential: $O(2^n \cdot m^n)$ in the worst case, which is far too slow for $n, m \le 2000$.

Optimal Approach

The key insight is that the problem can be solved using dynamic programming with a memoization technique. We can maintain a state defined by the current index in arr1 and the previous number in the increasing sequence. For each index, we have two options: keep arr1[i] if it is greater than the previous number, or replace it with the smallest number from arr2 that is greater than the previous number. To efficiently find the smallest replacement, we can sort arr2 and use binary search. By memoizing the results for each state, we avoid redundant computations, resulting in a much faster solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * m^n) O(n) Explores all replacement sequences recursively
Optimal O(n * m * log m) O(n * m) Uses DP with memoization and binary search in sorted arr2

Algorithm Walkthrough

  1. Sort arr2 and remove duplicates to facilitate efficient binary search. This ensures we can quickly find the smallest number in arr2 that is greater than any given value.
  2. Define a DP function dfs(index, prev) that represents the minimum number of operations required to make arr1[index:] strictly increasing given that the previous element was prev.
  3. Base case: if index equals the length of arr1, we have processed all elements and return 0 operations.
  4. Option 1 - Keep current element: if arr1[index] > prev, recursively call dfs(index + 1, arr1[index]). This represents the scenario where we do not replace the current element.
  5. Option 2 - Replace with element from arr2: use binary search on arr2 to find the smallest element greater than prev. If such an element exists, recursively call dfs(index + 1, arr2[j]) + 1 to account for the replacement operation.
  6. Memoize the result for each (index, prev) combination to avoid recomputation.
  7. Return the minimum operations from the two options. If both options are invalid, propagate infinity to indicate that it is impossible to make the array strictly increasing.
  8. Final result: call dfs(0, -1) (or any value smaller than the smallest possible element) and return -1 if the result is infinity.

Why it works: The DP function explores all valid paths using recursion but avoids redundant calculations through memoization. By always considering both keeping and replacing the current element, and using binary search for efficient replacements, the algorithm guarantees finding the minimal number of operations or correctly identifying impossibility.

Python Solution

from typing import List
import bisect
from functools import lru_cache

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        arr2 = sorted(set(arr2))  # Remove duplicates and sort for binary search

        @lru_cache(None)
        def dfs(index: int, prev: int) -> int:
            if index == len(arr1):
                return 0  # Reached the end

            min_ops = float('inf')

            # Option 1: Keep current element if strictly greater than prev
            if arr1[index] > prev:
                min_ops = dfs(index + 1, arr1[index])

            # Option 2: Replace with element from arr2
            j = bisect.bisect_right(arr2, prev)  # Find smallest element > prev
            if j < len(arr2):
                min_ops = min(min_ops, 1 + dfs(index + 1, arr2[j]))

            return min_ops

        result = dfs(0, -1)
        return result if result != float('inf') else -1

The implementation starts by preprocessing arr2 to allow fast lookup of replacement candidates. The dfs function handles each index recursively, exploring both keeping the element and replacing it using binary search. lru_cache memoizes results to avoid recomputation. The final call returns the minimal operations or -1 if impossible.

Go Solution

package main

import (
    "sort"
    "math"
)

func makeArrayIncreasing(arr1 []int, arr2 []int) int {
    arr2Map := map[int]bool{}
    for _, v := range arr2 {
        arr2Map[v] = true
    }
    arr2Unique := []int{}
    for k := range arr2Map {
        arr2Unique = append(arr2Unique, k)
    }
    sort.Ints(arr2Unique)

    memo := map[[2]int]int{}
    var dfs func(index int, prev int) int
    dfs = func(index int, prev int) int {
        if index == len(arr1) {
            return 0
        }
        key := [2]int{index, prev}
        if val, exists := memo[key]; exists {
            return val
        }

        minOps := math.MaxInt32

        // Option 1: Keep current element
        if arr1[index] > prev {
            minOps = dfs(index+1, arr1[index])
        }

        // Option 2: Replace from arr2
        j := sort.Search(len(arr2Unique), func(i int) bool { return arr2Unique[i] > prev })
        if j < len(arr2Unique) {
            temp := dfs(index+1, arr2Unique[j])
            if temp != math.MaxInt32 {
                minOps = min(minOps, 1+temp)
            }
        }

        memo[key] = minOps
        return minOps
    }

    res := dfs(0, -1)
    if res == math.MaxInt32 {
        return -1
    }
    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

The Go version handles memoization with a map using [2]int as the key. Sorting arr2 and using sort.Search allows efficient replacement lookup. The recursion and base case logic mirrors the Python implementation.

Worked Examples

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

index prev Keep Replace min_ops
0 -1 dfs(1,1)=... dfs(1,1)=... 0
1 1 Keep invalid Replace 2 -> dfs(2,2) 1
2 2 Keep 3 valid -> dfs(3,3) Replace 3 -> dfs(3,3) 1
3 3 Keep 6 -> dfs(4,6) Replace 4 -> dfs(4,4) 1
4 6 Keep 7 -> dfs(5,7)=0 Replace 7 -> dfs(5,7)=0 1

Result: 1

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

Similar reasoning, minimum operations = 2.

Example 3: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]

No valid replacement sequence possible, result = -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n * m