[
array
dynamic programming
sliding window
]
Leetcode 0487. Max Consecutive Ones II
Problem statement
https://leetcode.com/problems/max-consecutive-ones-ii/
Solution
Actually, what is asked is to find the window of maximum length, such that it has at most one 0
. One way is to use sliding window approach, where we move right side if number of 0
is not more than 1
and if it is, move left side until it becomes >= 1
.
Complexity
Time complexity is O(n)
, space complexity is O(1)
.
Code
class Solution:
def findMaxConsecutiveOnes(self, A):
ans, n, zeroes = 0, len(A), 0
beg, end = 0, 0
while end < n:
if end < n and zeroes + (A[end] == 0) <= 1:
zeroes += (A[end] == 0)
end += 1
ans = max(ans, end - beg)
else:
zeroes -= (A[beg] == 0)
beg += 1
return ans
Remark
There is also dp approach, where dp[i][j]
is the length of longest subarray of with j
zeros, such that it ends at point i
with O(n)
time complexity and O(n)
or O(1)
space complexity. See also almost the same Problem 1493 Longest Subarray of 1’s After Deleting One Element.