[Python] O(N) Time O(1) Space DP solution with explainations
For each pair of elements of A and B, (A[i], B[i]), there are only two status \'not swap\' or \'swap\'. Set two variables, n_swap, swap, to store the min number
For each pair of elements of A and B, (A[i], B[i]), there are only two status \'not swap\' or \'swap\'. Set two variables, n_swap, swap, to store the min number of swaps to make subarray A[:i+1] and B[:i+1] strict increasing. \n\nFor i-th pair of (A[i], B[i]), there are only three possible cases since it is guaranteed that at least an possible A and B exits after some swaps:\n\t1. (A[i], B[i]) and (A[i - 1], B[i - 1]) need to be the same status, i.e. if (i-1)th pair swap, i-th pair need to swap; if (i-1)th pair doesn\'t swap, i-th pair must not swap to satisfiy the strict increasing condition.\n\t2. (A[i], B[i]) and (A[i - 1], B[i - 1]) need to be the opposite status. i.e. if (i-1)th pair swap, then ith pair must not swap, vice versa.\n\t3. (A[i], B[i]) could be either same or opposite status of (A[i - 1], B[i - 1]), the strict increasing condition will be satisfied.\n\nHere is my code with comments:\n```\nclass Solution:\n    def minSwap(self, A: List[int], B: List[int]) -> int:\n        # to store min number of swaps of two status: not swap and swap\n        n_swap, swap = 0, 1\n        for i in range(1, len(A)):\n            # Case III: ith pair of (a, b) could be any status\n            if max(A[i - 1], B[i - 1]) < min(A[i], B[i]):\n                n_swap = min(n_swap, swap)\n                swap = n_swap + 1\n            # Case I: same status of ith and (i-1)th pair of (a, b)\n            elif A[i - 1] < A[i] and B[i - 1] < B[i]:\n                swap += 1\n            # Case I: diff status of ith and (i-1)th pair of (a, b)\n            else:\n                n_swap, swap = swap, n_swap + 1\n        return min(n_swap, swap)\n```\n\n
['Dynamic Programming', 'Python', 'Python3']