Complexity T : O(n) M : O(1)
class Solution(object):
def minSwap(self, A, B):
'''
:type A: List[int]
:type B: List[int]
:rtype: int
'''
keep, swap = 0, 1 # keep means no need to swap i th.
for i in range(1, len(A)):
if A[i - 1] >= B[i] or B[i - 1] >= A[i]:
'''
means the manipulation of A[2] and B[2] should be same as A[1] and B[1]
if A[1] and B[1] swap, A[2] and B[2] should swap
So swap += 1, keep = keep
'''
swap += 1
elif A[i - 1] >= A[i] or B[i - 1] >= B[i]:
'''
means the manipulation of A[3] and B[3] and A[2] and B[2] should be opposite.
In this case, swap = keep + 1, keep = swap(old)
'''
tmp = swap
swap = keep + 1
keep = tmp
else:
'''
means no need to change anything, so:
min = min(swap, keep)
swap = min + 1, keep = min
'''
m = min(swap, keep)
swap = m + 1
keep = m
return min(keep, swap)