Java neat and easy to understand DP O(n) solution!
We create a dp[n][2] array. dp[i][0] means the minimun swaps when we do not swap in position i, while dp[i][1] means otherwise.\n\nBasically, there are three ca
We create a dp[n][2] array. dp[i][0] means the minimun swaps when we do not swap in position i, while dp[i][1] means otherwise.\n\nBasically, there are three cases:\na) We either swap or not in position i for condition: A[i]>A[i-1] && A[i]>B[i-1] && B[i] > A[i-1] && B[i] > B[i-1].\nb) If i-1 swaps, i swaps. If i-1 does not swap, i does not swap. A[i]>A[i-1] && B[i]>B[i-1]\nc) If i-1 swaps, i does not swaps. If i-1 does not swap, i swaps.\n\n```\n\n    public int minSwap(int[] A, int[] B) {\n        int[][] dp = new int[A.length][2];\n        \n        dp[0][0] = 0;\n        dp[0][1] = 1;\n        \n        for(int i=1; i<A.length; i++) {\n            if(A[i]>A[i-1] && A[i]>B[i-1] && B[i] > A[i-1] && B[i] > B[i-1]) {\n                dp[i][0] = Math.min(dp[i-1][0], dp[i-1][1]);\n                dp[i][1] = Math.min(dp[i-1][0], dp[i-1][1])+1;\n            } else if (A[i]>A[i-1] && B[i]>B[i-1]) {\n                dp[i][0] = dp[i-1][0];\n                dp[i][1] = dp[i-1][1]+1;\n            } else {\n                dp[i][0] = dp[i-1][1];\n                dp[i][1] = dp[i-1][0]+1;\n            }\n        }\n\t\t\t\t\n        return Math.min(dp[A.length-1][0], dp[A.length-1][1]);\n    }\n\t\t\n\t\t\n\t\t\n```\n\nBelow is optimized O(1) space solution:\n\n```\n\n    public int minSwap(int[] A, int[] B) {\n        int pre_swap = 1, pre_not_swap = 0;\n        \n        for(int i=1; i<A.length; i++) {\n            int cur_swap, cur_not_swap;\n            if(A[i]>A[i-1] && A[i]>B[i-1] && B[i] > A[i-1] && B[i] > B[i-1]) {\n                cur_not_swap = Math.min(pre_swap, pre_not_swap);\n                cur_swap = Math.min(pre_swap, pre_not_swap)+1;\n            } else if (A[i]>A[i-1] && B[i]>B[i-1]) {\n                cur_not_swap = pre_not_swap;\n                cur_swap = pre_swap+1;\n            } else {\n                cur_not_swap = pre_swap;\n                cur_swap = pre_not_swap+1;\n            }\n            \n            pre_swap = cur_swap;\n            pre_not_swap = cur_not_swap;\n        }\n        \n        return Math.min(pre_swap, pre_not_swap);\n    }\n```
[]