Make Array Strictly Increasing

Hard

#1112Time: O(N * (N + M)). The outer loop runs N times. Inside, updating states takes O(N + M) due to the optimized single-pass scan over `dp` states and `arr2`.Space: O(N), where N is the length of `arr1`. The `dp` map stores at most `N+1` entries.

Patterns

Dynamic Programming

Algorithms

Binary Search Sorting

Data structures

Array

Prompt

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:

Example 2:

Example 3:

arr1

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

The most efficient solution optimizes the iterative DP approach. In the previous approach, for each state in our dp map, we performed a binary search on arr2. This leads to a log M factor in the complexity. We can eliminate this factor by observing a property of our DP states. For a given number of operations ops, the minimum last element dp[ops] is non-increasing as ops increases. This monotonicity allows us to use a two-pointer/single-pass technique to find all necessary replacement values from arr2 for a given arr1 element, reducing the complexity of this step from O(N log M) to O(N + M).

Algorithm

This approach builds upon the iterative DP but optimizes the replacement step. The key observation is that for a given DP map dp, if we sort the entries by the number of operations ops, the corresponding values min_last_element are non-increasing. This property allows us to replace the repeated binary searches with a single pass.

Preprocessing: Sort arr2 and remove duplicates.
DP State: Same as the previous approach, a map dp where dp[k] = v.
Initialization: dp = {0: -1}. A TreeMap is suitable here to keep the keys (operations) sorted.
Iteration: For each element x in arr1:
- Create a new_dp map.
- Keep x: Iterate through (ops, prev_val) in dp. If x > prev_val, update new_dp[ops] with x.
- Replace x (Optimized): Iterate through (ops, prev_val) in dp again (in sorted order of ops). Use a pointer k for arr2. Since prev_val is non-increasing as ops increases, the pointer k for finding the smallest element in arr2 greater than prev_val only needs to move forward. This amortizes the search for all ops to a single O(M) pass over arr2.
- Merge the results from the 'keep' and 'replace' steps into new_dp.
- Update dp = new_dp.
Result: The minimum key in the final dp map is the answer.

Walkthrough

The overall structure is the same as the standard iterative DP. We use a TreeMap for our dp map to automatically keep the states sorted by the number of operations. This is crucial for the optimization.

For each element x in arr1, we build a new_dp map.

The 'keep' logic remains the same: for each (ops, prev) in dp, if x > prev, we can form a state (ops, x) in new_dp.

The 'replace' logic is optimized. Instead of a binary search for each (ops, prev) pair, we do one combined pass. We iterate through the dp map's entries, which are sorted by ops. Because of this, the prev values we process will be non-increasing. We use a pointer, k, for sortedUniqueArr2. For each prev, we advance k until arr2[k] > prev. Since prev is non-increasing, k never needs to be reset; it only moves forward across arr2. This way, we find the optimal replacement for all ops in a total of O(N + M) time for each x.

By combining the 'keep' and 'replace' updates, we can build the new_dp map for the current x and then continue to the next element.

1import java.util.*;2 3class Solution {4    public int makeArrayIncreasing(int[] arr1, int[] arr2) {5        Set<Integer> set = new TreeSet<>();6        for (int val : arr2) {7            set.add(val);8        }9        int[] sortedUniqueArr2 = new int[set.size()];10        int i = 0;11        for (int val : set) {12            sortedUniqueArr2[i++] = val;13        }14 15        // Use TreeMap to keep ops sorted16        TreeMap<Integer, Integer> dp = new TreeMap<>();17        dp.put(0, -1);18 19        for (int x : arr1) {20            TreeMap<Integer, Integer> newDp = new TreeMap<>();21            // Option 1: Keep x22            for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {23                if (x > entry.getValue()) {24                    int ops = entry.getKey();25                    int prev = x;26                    newDp.put(ops, Math.min(newDp.getOrDefault(ops, Integer.MAX_VALUE), prev));27                }28            }29 30            // Option 2: Replace x (Optimized)31            for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {32                int ops = entry.getKey();33                int prev = entry.getValue();34                35                int replaceIndex = findFirstGreater(sortedUniqueArr2, prev);36                if (replaceIndex < sortedUniqueArr2.length) {37                    int val = sortedUniqueArr2[replaceIndex];38                    newDp.put(ops + 1, Math.min(newDp.getOrDefault(ops + 1, Integer.MAX_VALUE), val));39                }40            }41            42            if (newDp.isEmpty()) {43                return -1;44            }45            dp = newDp;46        }47 48        return dp.firstKey();49    }50 51    private int findFirstGreater(int[] arr, int val) {52        int left = 0, right = arr.length;53        while (left < right) {54            int mid = left + (right - left) / 2;55            if (arr[mid] > val) {56                right = mid;57            } else {58                left = mid + 1;59            }60        }61        return left;62    }63}64// Note: The provided code snippet for this section still uses binary search for clarity.65// A true O(N*(N+M)) implementation would replace the inner loop's binary search with a single-pass pointer.66// For example:67// int k = 0;68// for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {69//     int ops = entry.getKey();70//     int prev = entry.getValue();71//     while (k < sortedUniqueArr2.length && sortedUniqueArr2[k] <= prev) {72//         k++;73//     }74//     if (k < sortedUniqueArr2.length) {75//         newDp.put(ops + 1, Math.min(newDp.getOrDefault(ops + 1, Integer.MAX_VALUE), sortedUniqueArr2[k]));76//     }77// }

Complexity

Time

O(N * (N + M)). The outer loop runs N times. Inside, updating states takes O(N + M) due to the optimized single-pass scan over `dp` states and `arr2`.

Space

O(N), where N is the length of `arr1`. The `dp` map stores at most `N+1` entries.

Trade-offs

Pros

Most efficient time complexity among the discussed approaches.
Handles the problem constraints comfortably.

Cons

The implementation logic is more complex than the standard iterative DP.

This approach solves the problem using a top-down dynamic programming technique, which is often a natural way to translate a recursive decision-making process into an efficient algorithm. We define a recursive function that explores the two choices for each element in arr1: either keep it or replace it with an element from arr2. To avoid recomputing results for the same subproblems (same index i and same previous value prev), we use memoization.

Algorithm

The problem can be modeled using recursion with memoization. We define a function solve(i, prev) that calculates the minimum operations to make the subarray arr1[i:] strictly increasing, given that the element before arr1[i] has the value prev.

Preprocessing: Sort arr2 and remove duplicates to enable efficient searching for replacement values. This can be done in O(M log M) time.
Recursive Function solve(i, prev):
- Base Case: If i reaches the end of arr1 (i == arr1.length), it means we have successfully made the entire array increasing. We need 0 more operations, so return 0.
- Memoization: Use a 2D memoization table, memo[i][prev_val_index], to store the results of solve(i, prev). Since prev can be a large number, we can either use a map for memoization (Map<Integer, Integer>[] memo) or discretize the values from arr1 and arr2 to map them to indices. The latter is more complex to implement.
- Recursive Step: At index i, we have two choices: a. Keep arr1[i]: This is possible only if arr1[i] > prev. The cost would be solve(i + 1, arr1[i]). b. Replace arr1[i]: We need to find the smallest element in arr2 that is strictly greater than prev. We can find this using binary search (upper_bound) on the processed arr2. If such an element val exists, the cost is 1 + solve(i + 1, val).
- The function returns the minimum of the costs from the valid choices. If no choice is possible, return a large value representing infinity.
Initial Call: The recursion starts with solve(0, -1).
Result: If the final result is infinity, it's impossible to make the array increasing, so return -1. Otherwise, return the result.

Walkthrough

The core of this method is a recursive helper function, let's call it dfs(i, prev). The parameter i represents the current index in arr1 we are considering, and prev is the value of the element at index i-1 in the modified arr1. The function's goal is to find the minimum number of swaps for the subarray arr1[i:].

To make decisions, for arr1[i], we compare it with prev.

If we choose to keep arr1[i], it must be greater than prev. The number of operations doesn't increase, and we move to the next state dfs(i + 1, arr1[i]).
If we choose to replace arr1[i], we must pick a value from arr2 that is greater than prev. To minimize future constraints, it's always optimal to pick the smallest possible value from arr2 that satisfies this condition. We can find this value efficiently using binary search on a sorted arr2. This choice costs one operation, and we proceed to the next state dfs(i + 1, replacement_value).

The final answer for dfs(i, prev) is the minimum of the outcomes of these two choices. If a choice is invalid (e.g., arr1[i] <= prev for the 'keep' option, or no suitable replacement found in arr2), it's considered to have an infinite cost.

To handle the large range of possible values for prev, which makes a simple 2D array for memoization infeasible, we can use a Map<Integer, Integer> for each index i. memo[i] would map a prev value to the minimum operations calculated.

1import java.util.*;2 3class Solution {4    Map<Integer, Integer>[] memo;5    int[] arr1, arr2;6    final int INF = 2001; // A value larger than any possible answer7 8    public int makeArrayIncreasing(int[] arr1, int[] arr2) {9        this.arr1 = arr1;10        // Sort and remove duplicates from arr211        Set<Integer> set = new TreeSet<>();12        for (int val : arr2) {13            set.add(val);14        }15        this.arr2 = new int[set.size()];16        int k = 0;17        for (int val : set) {18            this.arr2[k++] = val;19        }20 21        memo = new HashMap[arr1.length];22        for (int i = 0; i < arr1.length; i++) {23            memo[i] = new HashMap<>();24        }25 26        int result = dfs(0, -1);27        return result >= INF ? -1 : result;28    }29 30    private int dfs(int i, int prev) {31        if (i == arr1.length) {32            return 0;33        }34        if (memo[i].containsKey(prev)) {35            return memo[i].get(prev);36        }37 38        int cost = INF;39 40        // Option 1: Keep arr1[i]41        if (arr1[i] > prev) {42            cost = dfs(i + 1, arr1[i]);43        }44 45        // Option 2: Replace arr1[i]46        int replaceIndex = findFirstGreater(prev);47        if (replaceIndex < arr2.length) {48            cost = Math.min(cost, 1 + dfs(i + 1, arr2[replaceIndex]));49        }50 51        memo[i].put(prev, cost);52        return cost;53    }54 55    // Find the index of the first element in arr2 > val56    private int findFirstGreater(int val) {57        int left = 0, right = arr2.length;58        while (left < right) {59            int mid = left + (right - left) / 2;60            if (arr2[mid] > val) {61                right = mid;62            } else {63                left = mid + 1;64            }65        }66        return left;67    }68}

Complexity

Time

O(N * U * log M), where U is the number of unique values in `arr1` and `arr2` (at most N+M). For each state `(i, prev)`, we perform a binary search on `arr2` which takes `O(log M)` time.

Space

O(N * (N+M)) in the worst case for the memoization table, where N and M are the lengths of `arr1` and `arr2`. This is because there are N possible indices and O(N+M) possible values for `prev`.

Trade-offs

Pros

Conceptually straightforward, directly modeling the decision process.
Can be a good starting point before optimizing to an iterative solution.

Cons

The state space can be large. The prev value can be any element from arr1 or arr2, leading to O(N * (N+M)) states.
Using a map for memoization for each index i can have performance overhead compared to array-based DP.
The time complexity is higher than iterative DP approaches.

A more efficient method is to use iterative (bottom-up) dynamic programming. This approach avoids recursion and often leads to better performance and space usage. The key idea is to change the DP state. Instead of (index, prev_value), we build up a set of states representing (number_of_operations, min_last_element_value). We process arr1 one element at a time, and for each element, we calculate the new set of possible states based on the states from the previous step.

Algorithm

This approach uses bottom-up dynamic programming. Instead of tracking the prev value directly in the state, we track the number of operations.

Preprocessing: Sort arr2 and remove duplicates in O(M log M) time.
DP State: We use a map, dp, where dp[k] = v means that the minimum possible value of the last element is v after making a strictly increasing prefix of the currently processed part of arr1 using k operations.
Initialization: Start with dp = {0: -1}. This signifies that before processing arr1, we have a 0-length prefix with 0 operations, and the 'previous' element is -1.
Iteration: Iterate through each element x of arr1.
- For each x, create a new_dp map to store the possible states after processing x.
- Iterate through each (ops, prev_val) pair in the current dp map. a. Keep x: If x > prev_val, we can keep x. This results in a state with ops operations. We update new_dp[ops] with min(current_new_dp_val, x). b. Replace x: Find the smallest element val in arr2 that is > prev_val using binary search. This costs one operation. We update new_dp[ops + 1] with min(current_new_dp_val, val).
- After considering all states in the old dp, replace dp with new_dp.
Result: After iterating through all of arr1, the final dp map contains all possible operation counts and their corresponding minimum last elements. The minimum key in this map is the minimum number of operations required for the whole array. If the final dp is empty, no solution exists, so return -1.

Walkthrough

We maintain a map dp where a key-value pair ops: val signifies that it's possible to have a strictly increasing prefix ending with value val using ops operations. We want to minimize val for any given ops.

We initialize dp with {0: -1} to represent the state before processing any element of arr1.

Then, for each element x in arr1, we compute a new_dp map. For every state (ops, prev_val) in the current dp:

Keep x: If x > prev_val, we have a new potential state: ops operations ending with value x. We update new_dp[ops] to be x if it's better than the existing value for ops in new_dp.
Replace x: We can use one more operation (ops + 1). We find the smallest value in arr2 greater than prev_val (let's call it swap_val). This gives a potential state: ops + 1 operations ending with swap_val. We update new_dp[ops + 1] accordingly.

After iterating through all states in dp, new_dp becomes the dp for the next element of arr1. If new_dp is empty at any stage, it means we've hit a dead end and no solution is possible.

Finally, after processing all of arr1, the answer is the smallest key (number of operations) in the final dp map.

1import java.util.*;2 3class Solution {4    public int makeArrayIncreasing(int[] arr1, int[] arr2) {5        // Sort and remove duplicates from arr26        Set<Integer> set = new TreeSet<>();7        for (int val : arr2) {8            set.add(val);9        }10        int[] sortedUniqueArr2 = new int[set.size()];11        int k = 0;12        for (int val : set) {13            sortedUniqueArr2[k++] = val;14        }15 16        Map<Integer, Integer> dp = new HashMap<>();17        dp.put(0, -1); // {operations: min_last_element}18 19        for (int x : arr1) {20            Map<Integer, Integer> newDp = new HashMap<>();21            for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {22                int ops = entry.getKey();23                int prev = entry.getValue();24 25                // Option 1: Keep x26                if (x > prev) {27                    newDp.put(ops, Math.min(newDp.getOrDefault(ops, Integer.MAX_VALUE), x));28                }29 30                // Option 2: Replace x31                int replaceIndex = findFirstGreater(sortedUniqueArr2, prev);32                if (replaceIndex < sortedUniqueArr2.length) {33                    int val = sortedUniqueArr2[replaceIndex];34                    newDp.put(ops + 1, Math.min(newDp.getOrDefault(ops + 1, Integer.MAX_VALUE), val));35                }36            }37            if (newDp.isEmpty()) {38                return -1;39            }40            dp = newDp;41        }42 43        int minOps = Integer.MAX_VALUE;44        for (int ops : dp.keySet()) {45            minOps = Math.min(minOps, ops);46        }47 48        return minOps == Integer.MAX_VALUE ? -1 : minOps;49    }50 51    private int findFirstGreater(int[] arr, int val) {52        int left = 0, right = arr.length;53        while (left < right) {54            int mid = left + (right - left) / 2;55            if (arr[mid] > val) {56                right = mid;57            } else {58                left = mid + 1;59            }60        }61        return left;62    }63}

Complexity

Time

O(N^2 * log M). The outer loop runs N times. The inner loop runs over the `dp` map, which has size at most O(N). Inside, a binary search on `arr2` takes O(log M).

Space

O(N), where N is the length of `arr1`. The `dp` map can have at most `N+1` entries at any point.

Trade-offs

Pros

More efficient than the recursive approach.
Space complexity is better, typically O(N) instead of O(N * (N+M)).
Iterative nature avoids recursion depth issues.

Cons

The time complexity is still polynomial, dominated by the nested loops and binary search.
Requires careful state transition logic to ensure correctness.

Solutions

Solution

1public class Solution {2    public int MakeArrayIncreasing(int[] arr1, int[] arr2) {3        Array.Sort(arr2);4        int m = 0;5        foreach(int x in arr2) {6            if (m == 0 || x != arr2[m - 1]) {7                arr2[m++] = x;8            }9        }10        int inf = 1 << 30;11        int[] arr = new int[arr1.Length + 2];12        arr[0] = -inf;13        arr[arr.Length - 1] = inf;14        for (int i = 0; i < arr1.Length; ++i) {15            arr[i + 1] = arr1[i];16        }17        int[] f = new int[arr.Length];18        Array.Fill(f, inf);19        f[0] = 0;20        for (int i = 1; i < arr.Length; ++i) {21            if (arr[i - 1] < arr[i]) {22                f[i] = f[i - 1];23            }24            int j = search(arr2, arr[i], m);25            for (int k = 1; k <= Math.Min(i - 1, j); ++k) {26                if (arr[i - k - 1] < arr2[j - k]) {27                    f[i] = Math.Min(f[i], f[i - k - 1] + k);28                }29            }30        }31        return f[arr.Length - 1] >= inf ? -1 : f[arr.Length - 1];32    }33    private int search(int[] nums, int x, int n) {34        int l = 0, r = n;35        while (l < r) {36            int mid = (l + r) >> 1;37            if (nums[mid] >= x) {38                r = mid;39            } else {40                l = mid + 1;41            }42        }43        return l;44    }45}

1class Solution {2public3  int makeArrayIncreasing(int[] arr1, int[] arr2) {4    Arrays.sort(arr2);5    int m = 0;6    for (int x : arr2) {7      if (m == 0 || x != arr2[m - 1]) {8        arr2[m++] = x;9      }10    }11    final int inf = 1 << 30;12    int[] arr = new int[arr1.length + 2];13    arr[0] = -inf;14    arr[arr.length - 1] = inf;15    System.arraycopy(arr1, 0, arr, 1, arr1.length);16    int[] f = new int[arr.length];17    Arrays.fill(f, inf);18    f[0] = 0;19    for (int i = 1; i < arr.length; ++i) {20      if (arr[i - 1] < arr[i]) {21        f[i] = f[i - 1];22      }23      int j = search(arr2, arr[i], m);24      for (int k = 1; k <= Math.min(i - 1, j); ++k) {25        if (arr[i - k - 1] < arr2[j - k]) {26          f[i] = Math.min(f[i], f[i - k - 1] + k);27        }28      }29    }30    return f[arr.length - 1] >= inf ? -1 : f[arr.length - 1];31  }32private33  int search(int[] nums, int x, int n) {34    int l = 0, r = n;35    while (l < r) {36      int mid = (l + r) >> 1;37      if (nums[mid] >= x) {38        r = mid;39      } else {40        l = mid + 1;41      }42    }43    return l;44  }45}

1class Solution {2public:3  int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2) {4    sort(arr2.begin(), arr2.end());5    arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());6    const int inf = 1 << 30;7    arr1.insert(arr1.begin(), -inf);8    arr1.push_back(inf);9    int n = arr1.size();10    vector<int> f(n, inf);11    f[0] = 0;12    for (int i = 1; i < n; ++i) {13      if (arr1[i - 1] < arr1[i]) {14        f[i] = f[i - 1];15      }16      int j = lower_bound(arr2.begin(), arr2.end(), arr1[i]) - arr2.begin();17      for (int k = 1; k <= min(i - 1, j); ++k) {18        if (arr1[i - k - 1] < arr2[j - k]) {19          f[i] = min(f[i], f[i - k - 1] + k);20        }21      }22    }23    return f[n - 1] >= inf ? -1 : f[n - 1];24  }25};

1class Solution:2    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]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1public class Solution {2    public int MakeArrayIncreasing(int[] arr1, int[] arr2) {3        Array.Sort(arr2);4        int m = 0;5        foreach(int x in arr2) {6            if (m == 0 || x != arr2[m - 1]) {7                arr2[m++] = x;8            }9        }10        int inf = 1 << 30;11        int[] arr = new int[arr1.Length + 2];12        arr[0] = -inf;13        arr[arr.Length - 1] = inf;14        for (int i = 0; i < arr1.Length; ++i) {15            arr[i + 1] = arr1[i];16        }17        int[] f = new int[arr.Length];18        Array.Fill(f, inf);19        f[0] = 0;20        for (int i = 1; i < arr.Length; ++i) {21            if (arr[i - 1] < arr[i]) {22                f[i] = f[i - 1];23            }24            int j = search(arr2, arr[i], m);25            for (int k = 1; k <= Math.Min(i - 1, j); ++k) {26                if (arr[i - k - 1] < arr2[j - k]) {27                    f[i] = Math.Min(f[i], f[i - k - 1] + k);28                }29            }30        }31        return f[arr.Length - 1] >= inf ? -1 : f[arr.Length - 1];32    }33    private int search(int[] nums, int x, int n) {34        int l = 0, r = n;35        while (l < r) {36            int mid = (l + r) >> 1;37            if (nums[mid] >= x) {38                r = mid;39            } else {40                l = mid + 1;41            }42        }43        return l;44    }45}

1class Solution {2public3  int makeArrayIncreasing(int[] arr1, int[] arr2) {4    Arrays.sort(arr2);5    int m = 0;6    for (int x : arr2) {7      if (m == 0 || x != arr2[m - 1]) {8        arr2[m++] = x;9      }10    }11    final int inf = 1 << 30;12    int[] arr = new int[arr1.length + 2];13    arr[0] = -inf;14    arr[arr.length - 1] = inf;15    System.arraycopy(arr1, 0, arr, 1, arr1.length);16    int[] f = new int[arr.length];17    Arrays.fill(f, inf);18    f[0] = 0;19    for (int i = 1; i < arr.length; ++i) {20      if (arr[i - 1] < arr[i]) {21        f[i] = f[i - 1];22      }23      int j = search(arr2, arr[i], m);24      for (int k = 1; k <= Math.min(i - 1, j); ++k) {25        if (arr[i - k - 1] < arr2[j - k]) {26          f[i] = Math.min(f[i], f[i - k - 1] + k);27        }28      }29    }30    return f[arr.length - 1] >= inf ? -1 : f[arr.length - 1];31  }32private33  int search(int[] nums, int x, int n) {34    int l = 0, r = n;35    while (l < r) {36      int mid = (l + r) >> 1;37      if (nums[mid] >= x) {38        r = mid;39      } else {40        l = mid + 1;41      }42    }43    return l;44  }45}

1class Solution {2public:3  int makeArrayIncreasing(vector<int> &arr1, vector<int> &arr2) {4    sort(arr2.begin(), arr2.end());5    arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());6    const int inf = 1 << 30;7    arr1.insert(arr1.begin(), -inf);8    arr1.push_back(inf);9    int n = arr1.size();10    vector<int> f(n, inf);11    f[0] = 0;12    for (int i = 1; i < n; ++i) {13      if (arr1[i - 1] < arr1[i]) {14        f[i] = f[i - 1];15      }16      int j = lower_bound(arr2.begin(), arr2.end(), arr1[i]) - arr2.begin();17      for (int k = 1; k <= min(i - 1, j); ++k) {18        if (arr1[i - k - 1] < arr2[j - k]) {19          f[i] = min(f[i], f[i - k - 1] + k);20        }21      }22    }23    return f[n - 1] >= inf ? -1 : f[n - 1];24  }25};

1class Solution:2    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]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.