• API
• FAQ
• Tools
• Archive
SHARE
TWEET Untitled a guest Oct 10th, 2019 115 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. public int makeArrayIncreasing(int[] arr1, int[] arr2) {
2.         int N = arr1.length, M = arr2.length;
3.
4.         Arrays.sort(arr2);
5.         int[][] dp = new int[N][M+1];
6.
7.         for (int j = 0; j < M; ++j) {
8.             dp[j] = 1;
9.         }
10.
11.         dp[M] = 0;
12.
13.         for (int i = 1; i < N; ++i) {
14.             Arrays.fill(dp[i], Integer.MAX_VALUE);
15.         }
16.
17.         for (int i = 1; i < N; ++i) {
18.             for (int j = 0; j <= M; ++j) {
19.                 for (int l = 0; l <= M; ++l) {
20.                     if (j < M) {
21.                         if ((l < j && arr2[l] < arr2[j]) ||
22.                            (l == M && arr1[i-1] < arr2[j]))
23.                             dp[i][j] = Math.min(dp[i][j], dp[i-1][l]+ 1) ;
24.                     } else {
25.                         if ((l < M && arr2[l] < arr1[i]) || (l == M && arr1[i-1] < arr1[i])) {
26.                             dp[i][j] = Math.min(dp[i][j], dp[i-1][l]);
27.                         }
28.                     }
29.
30.                 }
31.             }
32.         }
33.
34.         int ans = Integer.MAX_VALUE;
35.         for (int x:dp[N-1]) {
36.             ans = Math.min(ans, x);
37.         }
38.
39.         return ans == Integer.MAX_VALUE ? -1 : ans;
40.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top