Make Array Strictly Increasing

Share

Find minimum number of operations to make arr1 strictly increasing using values from arr2.

Example 1
Input: arr1=[1,5,3,6,7], arr2=[1,3,2,4] → Output: 1
Example 2
Input: arr1=[1,5,3,6,7], arr2=[4,3,1] → Output: 2
Example 3
Input: arr1=[1,5,3,6,7], arr2=[1,6,3,3] → Output: -1

Solution Approach

DP with sorted arr2. dp[v] = min ops to make arr1[0..i] valid with arr1[i]=v. Use TreeMap for state transitions.

  • Sort and deduplicate arr2
  • dp is TreeMap: previous last value -> ops count
  • For each arr1[i]: try keeping arr1[i] (if > prev) and replacing with each valid arr2 element
  • Track new states in next dp
  • Return minimum ops or -1 if empty
Java
public int makeArrayIncreasing(int[] arr1, int[] arr2) {
    Arrays.sort(arr2);
    TreeMap<Integer, Integer> dp = new TreeMap<>();
    dp.put(-1, 0);
    for (int a : arr1) {
        TreeMap<Integer, Integer> next = new TreeMap<>();
        // Keep arr1[i] if possible
        Map.Entry<Integer, Integer> lo = dp.lowerKey(a) != null ? dp.floorEntry(a-1) : null;
        if (lo != null) next.merge(a, lo.getValue(), Math::min);
        // Replace arr1[i] with something from arr2
        for (Map.Entry<Integer, Integer> e : dp.entrySet()) {
            int idx = Arrays.binarySearch(arr2, e.getKey() + 1);
            if (idx < 0) idx = -idx - 1;
            if (idx < arr2.length)
                next.merge(arr2[idx], e.getValue() + 1, Math::min);
        }
        if (next.isEmpty()) return -1;
        dp = next;
    }
    return Collections.min(dp.values());
}
  • Time Complexity: O(n*m*log m)
  • Space Complexity: O(m)