|
| 1 | +classSolution { |
| 2 | +publicintmakeArrayIncreasing(int[]arr1,int[]arr2) { |
| 3 | +Arrays.sort(arr2); |
| 4 | +Map<Pair<Integer,Integer>,Integer>dp =newHashMap<>(); |
| 5 | +intresult =dfs(0, -1,arr1,arr2,dp); |
| 6 | +returnresult <2001 ?result : -1; |
| 7 | + } |
| 8 | + |
| 9 | +privateintdfs(intidx,intprev,int[]arr1,int[]arr2,Map<Pair<Integer,Integer>,Integer>dp) { |
| 10 | +if (idx ==arr1.length) { |
| 11 | +return0; |
| 12 | + } |
| 13 | +if (dp.containsKey(newPair<>(idx,prev))) { |
| 14 | +returndp.get(newPair<>(idx,prev)); |
| 15 | + } |
| 16 | +intcost =2001; |
| 17 | +if (arr1[idx] >prev) { |
| 18 | +cost =dfs(idx +1,arr1[idx],arr1,arr2,dp); |
| 19 | + } |
| 20 | +intreplaceIdx =binarySearch(arr2,prev); |
| 21 | +if (replaceIdx <arr2.length) { |
| 22 | +cost =Math.min(cost,1 +dfs(idx +1,arr2[replaceIdx],arr1,arr2,dp)); |
| 23 | + } |
| 24 | +dp.put(newPair<>(idx,prev),cost); |
| 25 | +returncost; |
| 26 | + } |
| 27 | + |
| 28 | +privatestaticintbinarySearch(int[]arr,intvalue) { |
| 29 | +intleft =0; |
| 30 | +intright =arr.length; |
| 31 | +while (left <right) { |
| 32 | +intmid = (left +right) /2; |
| 33 | +if (arr[mid] <=value) { |
| 34 | +left =mid +1; |
| 35 | + }else { |
| 36 | +right =mid; |
| 37 | + } |
| 38 | + } |
| 39 | +returnleft; |
| 40 | + } |
| 41 | +} |