class Solution:
def minSwaps(self, data: List[int]) -> int:
# time O(N) space O(1)
# step1, count 1s, get window size
#size1 = 0
cnt_m = len(data) +1
# get window size
size1 = sum(data)
l, r = 0, 0
cnt = _max = 0
#step2, move right ptr until end of data
while r < len(data):
# step3, maintain a window size and cnt current 1s within window size
#if haven't reached window size, r + 1
while r < len(data) and r-l <size1:
# check if current ptr is 1, if yes, cnt + 1
if data[r] == 1:
cnt += 1
r+=1
#step4, update max cnt
_max = max(cnt, _max)
# step5, before proceed check boundry
# exit condition: r ptr reached end of data
if r == len(data):
break
# step6, move left and update current cnt
# check to be removed left ptr, if is 1, if yes, cnt -1
if data[l] == 1:
cnt -=1
# move left ptr
l += 1
return size1 - _max
concise code optimization, and also avoid multiple time checking if right potiner out of boundry
class Solution:
def minSwaps(self, data: List[int]) -> int:
# time O(N) space O(1)
max1,width,l,cnt = 0, sum(data),-1,0 # be careful with l initialized value. because index start from 0, so width = width -1 - (-1)
# step1, enumerate data and cnt each time val at pos r is 1
for r, val in enumerate(data):
cnt += val
#step2, check if r-l > window size, if yes, left ptr right move and update the cnt
if r-l > width:
l += 1
cnt -= data[l]
#step3, each time r/r&l ptr changes, update max 1s
max1 = max(max1,cnt)
# get minimun moves from maxmun 1s
return width-max1