Code Implementation

from bisect import bisect_right

class Solution:
    def makeArrayIncreasing(self, arr1, arr2):
        arr2 = sorted(set(arr2))
        dp = {-1: 0}  # key: previous value, value: operations count

        for num in arr1:
            new_dp = {}
            for prev in dp:
                # Option 1: Keep arr1[i] if it's strictly increasing
                if num > prev:
                    new_dp[num] = min(new_dp.get(num, float('inf')), dp[prev])
                # Option 2: Replace with the smallest element in arr2 > prev
                idx = bisect_right(arr2, prev)
                if idx < len(arr2):
                    new_dp[arr2[idx]] = min(new_dp.get(arr2[idx], float('inf')), dp[prev] + 1)
            dp = new_dp
            if not dp:
                return -1
        return min(dp.values())
      

#include <vector>
#include <algorithm>
#include <map>

using namespace std;

class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        sort(arr2.begin(), arr2.end());
        arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
        map<int, int> dp;
        dp[-1] = 0;
        for (int num : arr1) {
            map<int, int> new_dp;
            for (auto [prev, cnt] : dp) {
                // Option 1: Keep arr1[i]
                if (num > prev) {
                    if (!new_dp.count(num) || new_dp[num] > cnt)
                        new_dp[num] = cnt;
                }
                // Option 2: Replace with arr2 element
                auto it = upper_bound(arr2.begin(), arr2.end(), prev);
                if (it != arr2.end()) {
                    int v = *it;
                    if (!new_dp.count(v) || new_dp[v] > cnt + 1)
                        new_dp[v] = cnt + 1;
                }
            }
            dp = new_dp;
            if (dp.empty()) return -1;
        }
        int res = INT_MAX;
        for (auto [k, v] : dp) res = min(res, v);
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int num : arr2) set.add(num);
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(-1, 0);

        for (int num : arr1) {
            Map<Integer, Integer> newDp = new HashMap<>();
            for (int prev : dp.keySet()) {
                // Option 1: Keep arr1[i]
                if (num > prev) {
                    newDp.put(num, Math.min(newDp.getOrDefault(num, Integer.MAX_VALUE), dp.get(prev)));
                }
                // Option 2: Replace with arr2 element
                Integer next = set.higher(prev);
                if (next != null) {
                    newDp.put(next, Math.min(newDp.getOrDefault(next, Integer.MAX_VALUE), dp.get(prev) + 1));
                }
            }
            dp = newDp;
            if (dp.isEmpty()) return -1;
        }
        int res = Integer.MAX_VALUE;
        for (int val : dp.values()) res = Math.min(res, val);
        return res;
    }
}
      

var makeArrayIncreasing = function(arr1, arr2) {
    arr2 = Array.from(new Set(arr2)).sort((a, b) => a - b);
    let dp = new Map();
    dp.set(-1, 0);

    for (let num of arr1) {
        let newDp = new Map();
        for (let [prev, cnt] of dp.entries()) {
            // Option 1: Keep arr1[i]
            if (num > prev) {
                if (!newDp.has(num) || newDp.get(num) > cnt)
                    newDp.set(num, cnt);
            }
            // Option 2: Replace with arr2 element
            let l = 0, r = arr2.length;
            while (l < r) {
                let m = (l + r) >> 1;
                if (arr2[m] > prev) r = m;
                else l = m + 1;
            }
            if (l < arr2.length) {
                let v = arr2[l];
                if (!newDp.has(v) || newDp.get(v) > cnt + 1)
                    newDp.set(v, cnt + 1);
            }
        }
        dp = newDp;
        if (dp.size === 0) return -1;
    }
    return Math.min(...dp.values());
};
      

Problem Description

Given two integer arrays arr1 and arr2, your task is to make arr1 strictly increasing by performing the minimum number of operations. In one operation, you can replace any element in arr1 with any element from arr2.

• You cannot reuse the same element from arr2 more than once for replacements.
• After all replacements, arr1 must be strictly increasing (i.e., arr1[i] < arr1[i+1] for all valid i).
• If it is impossible to make arr1 strictly increasing, return -1.
• Assume there is at most one valid solution for each input.

Thought Process

The most direct approach is to try all possible ways to replace elements in arr1 with elements from arr2 and check if the result is strictly increasing. However, this brute-force method quickly becomes infeasible as the arrays grow, due to the huge number of combinations.

To optimize, we realize that at each index, we have two choices:

• Keep the current arr1[i] if it keeps the sequence strictly increasing.
• Replace arr1[i] with an unused element from arr2 that is larger than the previous element.

By using data structures that allow us to quickly find the next suitable element in arr2 (like sorting and binary search), we can cut down redundant checks and speed up the process.

Solution Approach

Let's break down the steps to solve this problem efficiently:

1. Sort and deduplicate arr2:
   • We sort arr2 and remove duplicates to make binary search possible and avoid reusing the same value.
2. Dynamic Programming State:
   • We use a dictionary (or map) dp where the key is the "previous value" used in the sequence, and the value is the minimum number of operations to reach this state.
   • We initialize dp with -1: 0, meaning before the first element, the previous value is effectively -1 and no operation has been performed.
3. Iterate through arr1:
   • For each number in arr1, we create a new new_dp map to store possible states for the current position.
   • For each state in dp, we consider two options:
     • If the current number is greater than the previous value, we can keep it. Update new_dp accordingly.
     • Otherwise, or in addition, we look for the smallest element in arr2 that is greater than the previous value (using binary search). If found, we can replace the current number with it (counting as one operation).
4. Update and Prune States:
   • After processing each position, we set dp = new_dp.
   • If dp is empty, it means no valid sequence is possible from here, so we return -1.
5. Result:
   • After processing all elements, the minimum value in dp.values() gives the minimum operations needed.

This approach is efficient because:

• We only keep the best (least operations) for each possible previous value.
• Binary search in arr2 is fast due to sorting.

Example Walkthrough

Let's work through an example:

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

1. Sort arr2: [1,2,3,4]
2. Initialization: dp = {-1: 0}
3. First element (1):
   • 1 > -1, so keep 1: new_dp[1] = 0
   • Find arr2 element > -1: 1. Replace: new_dp[1] = min(0, 1) (already 0)
4. Second element (5):
   • From prev = 1:
     • 5 > 1, keep: new_dp[5] = 0
     • arr2 element > 1: 2,3,4. Try 2: new_dp[2] = 1
5. Third element (3):
   • From prev = 5:
     • 3 <= 5, can't keep.
     • arr2 element > 5: none. Can't replace.
   • From prev = 2:
     • 3 > 2, keep: new_dp[3] = 1
     • arr2 element > 2: 3,4. Try 3: new_dp[3] = min(1,2) (already 1), try 4: new_dp[4] = 2
6. Fourth element (6):
   • From prev = 3:
     • 6 > 3, keep: new_dp[6] = 1
     • arr2 element > 3: 4. Replace: new_dp[4] = 2
   • From prev = 4:
     • 6 > 4, keep: new_dp[6] = min(1,2) (already 1)
     • arr2 element > 4: none.
7. Fifth element (7):
   • From prev = 6:
     • 7 > 6, keep: new_dp[7] = 1
     • arr2 element > 6: none.
   • From prev = 4:
     • 7 > 4, keep: new_dp[7] = min(1,2) (already 1)

The minimum number of operations is 1 (replace 5 with 2).

Time and Space Complexity

• Brute-force:
  • Try all combinations: O(2^n) possibilities, where n is the length of arr1.
• Optimized DP:
  • For each position, we may have up to O(m) possible previous values (where m is the length of arr2), and for each we do O(log m) binary search.
  • Total time: O(n * m * log m).
  • Space: O(n * m) for the DP map.
• Why?
  • Because we only store the best (minimum operations) for each possible previous value, the state space is pruned and efficient.

Summary

The key insight is to use dynamic programming to track, at each step, the minimum number of operations needed for each possible "previous value" in the strictly increasing sequence. By sorting arr2 and using binary search, we efficiently find replacement candidates. This approach transforms an exponential brute-force problem into a manageable one, leveraging both state pruning and fast lookups, resulting in an elegant and efficient solution.