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.