Untitled

import java.util.*;

public class Solution {
    // Memoization map to store results for subproblems
    private Map<String, Integer> memo;

    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        // Sort and remove duplicates from arr2
        Arrays.sort(arr2);
        List<Integer> sortedArr2 = new ArrayList<>();
        for (int num : arr2) {
            if (sortedArr2.isEmpty() || sortedArr2.get(sortedArr2.size() - 1) != num) {
                sortedArr2.add(num);
            }
        }

        // Initialize memoization map
        memo = new HashMap<>();

        // Start recursion from index 0 with no previous value (-1 indicates no previous value)
        int result = solve(0, arr1, sortedArr2, Integer.MIN_VALUE);

        // If result is still MAX, it means it's impossible to make arr1 strictly increasing
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    private int solve(int idx, int[] arr1, List<Integer> arr2, int prev) {
        // Base case: if we reach the end of arr1, no more operations are needed
        if (idx == arr1.length) {
            return 0;
        }

        // Create a unique key for the current state (idx, prev)
        String key = idx + "_" + prev;

        // Check if the result for this state is already computed
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        // Option 1: Keep arr1[idx] if it's greater than the previous value
        int result1 = Integer.MAX_VALUE;
        if (arr1[idx] > prev) {
            result1 = solve(idx + 1, arr1, arr2, arr1[idx]);
        }

        // Option 2: Replace arr1[idx] with the smallest value from arr2 that is greater than prev
        int result2 = Integer.MAX_VALUE;
        int replacementIndex = binarySearch(arr2, prev); // Find the smallest value > prev in arr2
        if (replacementIndex != -1) {
            result2 = 1 + solve(idx + 1, arr1, arr2, arr2.get(replacementIndex));
        }

        // Take the minimum of the two options
        int minOperations = Math.min(result1, result2);

        // Store the result in the memo map
        memo.put(key, minOperations);

        return minOperations;
    }

    // Helper function to perform binary search on arr2
    private int binarySearch(List<Integer> arr2, int target) {
        int left = 0, right = arr2.size() - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr2.get(mid) > target) {
                result = mid; // Potential candidate
                right = mid - 1; // Look for smaller candidates
            } else {
                left = mid + 1; // Move to the right half
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // Example 1
        int[] arr1_1 = {1, 5, 3, 6, 7};
        int[] arr2_1 = {1, 3, 2, 4};
        System.out.println(solution.makeArrayIncreasing(arr1_1, arr2_1)); // Output: 1

        // Example 2
        int[] arr1_2 = {1, 5, 3, 6, 7};
        int[] arr2_2 = {4, 3, 1};
        System.out.println(solution.makeArrayIncreasing(arr1_2, arr2_2)); // Output: 2

        // Example 3
        int[] arr1_3 = {1, 5, 3, 6, 7};
        int[] arr2_3 = {1, 6, 3, 3};
        System.out.println(solution.makeArrayIncreasing(arr1_3, arr2_3)); // Output: -1
    }
}