Make Array Strictly Increasing

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

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.

1. Preprocessing: Sort arr2 and remove duplicates.
2. DP State: Same as the previous approach, a map dp where dp[k] = v.
3. Initialization: dp = {0: -1}. A TreeMap is suitable here to keep the keys (operations) sorted.
4. 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.
5. Result: The minimum key in the final dp map is the answer.

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.

import java.util.*;

class Solution {
    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        Set<Integer> set = new TreeSet<>();
        for (int val : arr2) {
            set.add(val);
        }
        int[] sortedUniqueArr2 = new int[set.size()];
        int i = 0;
        for (int val : set) {
            sortedUniqueArr2[i++] = val;
        }

        // Use TreeMap to keep ops sorted
        TreeMap<Integer, Integer> dp = new TreeMap<>();
        dp.put(0, -1);

        for (int x : arr1) {
            TreeMap<Integer, Integer> newDp = new TreeMap<>();
            // Option 1: Keep x
            for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {
                if (x > entry.getValue()) {
                    int ops = entry.getKey();
                    int prev = x;
                    newDp.put(ops, Math.min(newDp.getOrDefault(ops, Integer.MAX_VALUE), prev));
                }
            }

            // Option 2: Replace x (Optimized)
            for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {
                int ops = entry.getKey();
                int prev = entry.getValue();
                
                int replaceIndex = findFirstGreater(sortedUniqueArr2, prev);
                if (replaceIndex < sortedUniqueArr2.length) {
                    int val = sortedUniqueArr2[replaceIndex];
                    newDp.put(ops + 1, Math.min(newDp.getOrDefault(ops + 1, Integer.MAX_VALUE), val));
                }
            }
            
            if (newDp.isEmpty()) {
                return -1;
            }
            dp = newDp;
        }

        return dp.firstKey();
    }

    private int findFirstGreater(int[] arr, int val) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > val) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
// Note: The provided code snippet for this section still uses binary search for clarity.
// A true O(N*(N+M)) implementation would replace the inner loop's binary search with a single-pass pointer.
// For example:
// int k = 0;
// for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {
//     int ops = entry.getKey();
//     int prev = entry.getValue();
//     while (k < sortedUniqueArr2.length && sortedUniqueArr2[k] <= prev) {
//         k++;
//     }
//     if (k < sortedUniqueArr2.length) {
//         newDp.put(ops + 1, Math.min(newDp.getOrDefault(ops + 1, Integer.MAX_VALUE), sortedUniqueArr2[k]));
//     }
// }