main idea: sliding window
# time O(N) space O(1)
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
cnt1 = 0
res = 0
n = len(nums)
l=r= 0
while r < n:
if nums[r]==1:
cnt1 += 1
res = max(cnt1,res)
while r-l +1- cnt1 == 2:
if nums[l] == 1:
cnt1 -= 1
l += 1
r+=1
return res if n != res else res-1 # edge case [1,1,1,1,1]
instead of tracking 1s, we can check only 0s, and update max_v after k is valid
class Solution:
def longestSubarray(self, A: List[int]) -> int:
k = 1
l = 0
n = len(A)
res = 0
for r in range(n):
k -= A[r] == 0
while k < 0:
if A[l] == 0:
k += 1
l += 1
res = max(res, r-l)
# print(l,r)
# print(f'window size: {r-l+1}')
return res
winodow size that doesn’t shrink
class Solution:
def longestSubarray(self, A: List[int]) -> int:
k = 1
l = 0
n = len(A)
for r in range(n):
k -= A[r] == 0
if k < 0:
k += A[l]==0
l += 1
#print(l,r)
#print(f'window size: {r-l+1}')
return r-l