Python 14-line O(1) space O(n) time DP solution
This problem can be solved using dynamic programming, at each position, we can choose to swap or not. Since we want two sorted arrays, at each position, whether
This problem can be solved using dynamic programming, at each position, we can choose to swap or not. Since we want two sorted arrays, at each position, whether to swap or not depends on the choice at previous position, so we can form a recursive formula.\n\n```\nN = len(A)\ndp = [[maxint]*2 for _ in range(N)]\n```\n\nLet initialize a N*2 array dp, \n\n* dp[i][0] means the least swaps used to make A[:i+1] and B[:i+1] sorted having no swap at i-th position.\n* dp[i][1] means the least swaps used to make A[:i+1] and B[:i+1] sorted having swap at i-th position.\n\n**Picture explanation:**\n![image](https://s3-lc-upload.s3.amazonaws.com/users/luckypants/image_1521451802.png)\n\n\nHere is the recursive formula:\n\nThere are two cases that can make the two arrays sorted:\n\n```\nA . B\nC . D\n```\n\nHere our cases are `A<B and C<D`  and `A<D and C<B`.\n\nBecause the possible combination to be sorted are only `A B` in array1 `C D` in array2 or `A D` in array1 `C B` in array2, so only the 2 cases, and they can holds at the same time: for example `A=1, B=2, C=1, D=2`. If both don\'t hold, swapping can\'t make them in order.\n\nFor $i in [1, N]$:\n\nIf A[i]>A[i-1] and B[i]>B[i-1] (they are in order without swap):\ndp[i][0]=min(dp[i][0], dp[i-1][0]) (no swap at i-1 and no swap at i)\ndp[i][1]=min(dp[i][1], dp[i-1][1]+1) (swap at i-1 so swap at i to make in order)\n\nIf A[i]>B[i-1] and B[i]>A[i-1] (they are in order with a swap):\ndp[i][0]=min(dp[i][0], dp[i-1][1]) (swap at i-1, no need to swap at i)\ndp[i][1]=min(dp[i][1], dp[i-1][0]+1) (no swap at i-1, so swap at i)\n\nThe two cases don\'t conflict with each other, so we choose minimum of them when both holds.\n\nWhat we want to return is min(dp[N-1][0], dp[N-1][1]).\n\nAt every recursion, we only need the last result, so we can use less space, from O(N) to O(1), time complexity O(N).\n\n20-Line Python Solution\uFF1A\n\n```\ndef minSwap(self, A, B):\n    """\n    :type A: List[int]\n    :type B: List[int]\n    :rtype: int\n    """\n    n = len(A)\n    pre = [0, 1]\n    for i in range(1, n):\n        cur = [sys.maxsize, sys.maxsize]\n        if A[i]>A[i-1] and B[i]>B[i-1]:\n            cur[0] = min(cur[0], pre[0])\n            cur[1] = min(cur[1], pre[1]+1)\n        if A[i]>B[i-1] and B[i]>A[i-1]:\n            cur[0] = min(cur[0], pre[1])\n            cur[1] = min(cur[1], pre[0]+1)\n        pre = cur\n        return min(pre)\n```
[]