[Java/C++/Python] DP O(N) Solution
Explanation\nswap[n] means the minimum swaps to make the A[i] and B[i] sequences increasing for 0 <= i <= n,\nin condition that we swap A[n] and B[n]\nnot_swap[
# **Explanation**\n```swap[n]``` means the minimum swaps to make the ```A[i]``` and ```B[i]``` sequences increasing for ```0 <= i <= n```,\nin condition that we swap ```A[n]``` and ```B[n]```\n```not_swap[n]``` is the same with ```A[n]``` and ```B[n]``` not swapped.\n\n@Acker help explain:\n1. `A[i - 1] < A[i] && B[i - 1] < B[i]`.\nIn this case, if we want to keep A and B increasing before the index i, can only have two choices.\n-> 1.1 don\'t swap at (i-1) and don\'t swap at i, we can get `not_swap[i] = not_swap[i-1]`\n-> 1.2 swap at (i-1) and swap at i, we can get `swap[i] = swap[i-1]+1`\nif swap at (i-1) and do not swap at i, we can not guarantee A and B increasing.\n\n2. `A[i-1] < B[i] && B[i-1] < A[i]`\nIn this case, if we want to keep A and B increasing before the index i, can only have two choices.\n-> 2.1 swap at (i-1) and do not swap at i, we can get `notswap[i] = Math.min(swap[i-1], notswap[i] )`\n-> 2.2 do not swap at (i-1) and swap at i, we can get `swap[i]=Math.min(notswap[i-1]+1, swap[i])`\n<br>\n\n# Complexty\nTime `O(N)`\nSpace `O(N)`\n<br>\n\n**C++**\n```cpp\n    int minSwap(vector<int>& A, vector<int>& B) {\n        int N = A.size();\n        int not_swap[1000] = {0};\n        int swap[1000] = {1};\n        for (int i = 1; i < N; ++i) {\n            not_swap[i] = swap[i] = N;\n            if (A[i - 1] < A[i] && B[i - 1] < B[i]) {\n                swap[i] = swap[i - 1] + 1;\n                not_swap[i] = not_swap[i - 1];\n            }\n            if (A[i - 1] < B[i] && B[i - 1] < A[i]) {\n                swap[i] = min(swap[i], not_swap[i - 1] + 1);\n                not_swap[i] = min(not_swap[i], swap[i - 1]);\n            }\n        }\n        return min(swap[N - 1], not_swap[N - 1]);\n    }\n```\n**Java**\n```java\n    public int minSwap(int[] A, int[] B) {\n        int N = A.length;\n        int[] swap = new int[1000];\n        int[] not_swap = new int[1000];\n        swap[0] = 1;\n        for (int i = 1; i < N; ++i) {\n            not_swap[i] = swap[i] = N;\n            if (A[i - 1] < A[i] && B[i - 1] < B[i]) {\n                swap[i] = swap[i - 1] + 1;\n                not_swap[i] = not_swap[i - 1];\n            }\n            if (A[i - 1] < B[i] && B[i - 1] < A[i]) {\n                swap[i] = Math.min(swap[i], not_swap[i - 1] + 1);\n                not_swap[i] = Math.min(not_swap[i], swap[i - 1]);\n            }\n        }\n        return Math.min(swap[N - 1], not_swap[N - 1]);\n    }\n```\n**Python**\n```py\n    def minSwap(self, A, B):\n        N = len(A)\n        not_swap, swap = [N] * N, [N] * N\n        not_swap[0], swap[0] = 0, 1\n        for i in range(1, N):\n            if A[i - 1] < A[i] and B[i - 1] < B[i]:\n                swap[i] = swap[i - 1] + 1\n                not_swap[i] = not_swap[i - 1]\n            if A[i - 1] < B[i] and B[i - 1] < A[i]:\n                swap[i] = min(swap[i], not_swap[i - 1] + 1)\n                not_swap[i] = min(not_swap[i], swap[i - 1])\n        return min(swap[-1], not_swap[-1])\n```\n<br>\n\n# Solution 2\nTime O(N)\nSpace only `O(1)`\n**Java**\n```java\n    public int minSwap(int[] A, int[] B) {\n        int N = A.length;\n        int swap = 1, not_swap = 0;\n        for (int i = 1; i < N; ++i) {\n            int not_swap2 = N, swap2 = N;\n            if (A[i - 1] < A[i] && B[i - 1] < B[i]) {\n                swap2 = swap + 1;\n                not_swap2 = not_swap;\n            }\n            if (A[i - 1] < B[i] && B[i - 1] < A[i]) {\n                swap2 = Math.min(swap2, not_swap + 1);\n                not_swap2 = Math.min(not_swap2, swap);\n            }\n            swap = swap2;\n            not_swap = not_swap2;\n        }\n        return Math.min(swap, not_swap);\n    }\n```\n**C++**\n```cpp\n    int minSwap(vector<int>& A, vector<int>& B) {\n        int N = A.size(), swap = 1, not_swap = 0;\n        for (int i = 1; i < N; ++i) {\n            int not_swap2 = N, swap2 = N;\n            if (A[i - 1] < A[i] && B[i - 1] < B[i]) {\n                swap2 = swap + 1;\n                not_swap2 = not_swap;\n            }\n            if (A[i - 1] < B[i] && B[i - 1] < A[i]) {\n                swap2 = min(swap2, not_swap + 1);\n                not_swap2 = min(not_swap2, swap);\n            }\n            swap = swap2;\n            not_swap = not_swap2;\n        }\n        return min(swap, not_swap);\n    }\n```\n**Python**\n```py\n    def minSwap(self, A, B):\n        N = len(A)\n        not_swap, swap = 0, 1\n        for i in range(1, N):\n            not_swap2 = swap2 = N\n            if A[i - 1] < A[i] and B[i - 1] < B[i]:\n                swap2 = swap + 1\n                not_swap2 = not_swap\n            if A[i - 1] < B[i] and B[i - 1] < A[i]:\n                swap2 = min(swap2, not_swap + 1)\n                not_swap2 = min(not_swap2, swap)\n            swap, not_swap = swap2, not_swap2\n        return min(swap, not_swap)\n```
[]