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[0][j] = 1;
  9.         }
  10.        
  11.         dp[0][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. OK, I Understand
 
Top