Find minimum number of operations to make arr1 strictly increasing using values from arr2.
Input: arr1=[1,5,3,6,7], arr2=[1,3,2,4] → Output: 1
Input: arr1=[1,5,3,6,7], arr2=[4,3,1] → Output: 2
Input: arr1=[1,5,3,6,7], arr2=[1,6,3,3] → Output: -1
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
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)