package leetcode;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/
 */
public class Problem801 {
    public int minSwap(int[] A, int[] B) {
        int answer = 0;
        int i = 0;
        int j = 0;
        while (i < A.length && j < B.length) {
            while (i + 1 < A.length && A[i] < A[i + 1]) {
                i++;
            }
            while (j + 1 < B.length && B[j] < B[j + 1]) {
                j++;
            }
            boolean swap = (i + 1 < A.length && A[i] >= A[i + 1]) ||
                (j + 1 < B.length && B[j] >= B[j + 1]);
            if (swap) {
                if (i < j) {
                    swap(A, B, i + 1);
                    j = i;
                    answer++;
                } else if (i > j) {
                    swap(A, B, j + 1);
                    i = j;
                    answer++;
                } else {
                    swap(A, B, i + 1);
                    answer++;
                }
            }
            i++;
            j++;
        }
        System.out.println(Arrays.toString(A));
        System.out.println(Arrays.toString(B));
        return answer;
    }

    private static void swap(int[] a, int[] b, int i) {
        int tmp = a[i];
        a[i] = b[i];
        b[i] = tmp;
    }

    public static void main(String[] args) {
        Problem801 prob = new Problem801();
//        System.out.println(prob.minSwap(new int[]{1, 3, 5, 4}, new int[]{1, 2, 3, 7})); // 1
//        System.out.println(prob.minSwap(new int[]{1, 3, 5, 4, 8}, new int[]{1, 2, 3, 7, 5})); // 1
        System.out.println(prob.minSwap(new int[]{0, 4, 4, 5, 9}, new int[]{0, 1, 6, 8, 10})); // 1
    }
}

@@ -16,34 +16,8 @@
 e;%0A%0A
-import java.util.Arrays;%0A%0A
 /**%0A
@@ -178,105 +178,209 @@
     
-int answer = 0;%0A        int i = 0;%0A        int j = 0
+Integer%5B%5D%5B%5D memo = new Integer%5BA.length%5D%5B2%5D; // 0 = no-swap, 1 = swap%0A        return minSwap(A, B, 0, 0, memo)
 ;%0A    
+%7D%0A%0A
     
-while (i %3C A.length && j %3C B.length
+private static int minSwap(int%5B%5D a, int%5B%5D b, int i, int swap, Integer%5B%5D%5B%5D memo
 ) %7B%0A
@@ -391,54 +391,25 @@
     
-    while (i + 1 %3C A.length && A%5Bi%5D %3C A%5Bi + 1%5D
+if (i == a.length
 ) %7B%0A
@@ -412,39 +412,40 @@
 ) %7B%0A            
-    i++
+return 0
 ;%0A            %7D%0A
@@ -430,36 +430,32 @@
 turn 0;%0A        
-    
 %7D%0A            wh
@@ -452,307 +452,239 @@
     
-    while (j + 1 %3C B.length && B%5Bj%5D %3C B%5Bj + 1%5D) %7B%0A                j++;%0A            %7D%0A            boolean swap = (i + 1 %3C A.length && A%5Bi%5D %3E= A%5Bi + 1%5D) %7C%7C%0A                (j + 1 %3C B.length && B%5Bj%5D %3E= B%5Bj + 1%5D);%0A            if (swap) %7B%0A                if (i %3C j) %7B%0A                    s
+if (memo%5Bi%5D%5Bswap%5D != null) %7B%0A            return memo%5Bi%5D%5Bswap%5D;%0A        %7D%0A        int min = Integer.MAX_VALUE;%0A        if (i == 0 %7C%7C a%5Bi%5D %3E a%5Bi - 1%5D && b%5Bi%5D %3E b%5Bi - 1%5D) %7B%0A            min = Math.min(min, minS
 wap(
-A, B
+a, b
 , i + 1
+, 0, memo)
 );%0A 
@@ -686,32 +686,34 @@
 ));%0A        
+%7D%0A
         
     j = i;%0A 
@@ -704,81 +704,56 @@
     
-    j = i;%0A                    answer++;%0A                %7D else if (i %3E j
+if (i == 0 %7C%7C a%5Bi%5D %3E b%5Bi - 1%5D && b%5Bi%5D %3E a%5Bi - 1%5D
 ) %7B%0A
@@ -768,32 +768,20 @@
     
-        
 swap(
-A, B, j + 1
+a, b, i
 );%0A 
@@ -795,81 +795,64 @@
     
-        i = j;%0A                    answer++;%0A                %7D else %7B%0A   
+min = Math.min(min, minSwap(a, b, i + 1, 1, memo) + 1);%0A
     
@@ -863,232 +863,73 @@
     
-     
 swap(
-A, B, i + 1);%0A                    answer++;%0A                %7D%0A            %7D%0A            i++;%0A            j++;%0A        %7D%0A        System.out.println(Arrays.toString(A));%0A        System.out.println(Arrays.toString(B))
+a, b, i); // backtrack%0A        %7D%0A        memo%5Bi%5D%5Bswap%5D = min
 ;%0A  
@@ -945,14 +945,11 @@
 urn 
-answer
+min
 ;%0A  
@@ -1083,399 +1083,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem801 prob = new Problem801();%0A//        System.out.println(prob.minSwap(new int%5B%5D%7B1, 3, 5, 4%7D, new int%5B%5D%7B1, 2, 3, 7%7D)); // 1%0A//        System.out.println(prob.minSwap(new int%5B%5D%7B1, 3, 5, 4, 8%7D, new int%5B%5D%7B1, 2, 3, 7, 5%7D)); // 1%0A        System.out.println(prob.minSwap(new int%5B%5D%7B0, 4, 4, 5, 9%7D, new int%5B%5D%7B0, 1, 6, 8, 10%7D)); // 1%0A    %7D
 %0A%7D%0A

Solve problem 801