Welcome to Subscribe On Youtube
487. Max Consecutive Ones II
Description
Given a binary array nums
, return the maximum number of consecutive 1
's in the array if you can flip at most one 0
.
Example 1:
Input: nums = [1,0,1,1,0] Output: 4 Explanation:  If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.  If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones. The max number of consecutive ones is 4.
Example 2:
Input: nums = [1,0,1,1,0,1] Output: 4 Explanation:  If we flip the first zero, nums becomes [1,1,1,1,0,1] and we have 4 consecutive ones.  If we flip the second zero, nums becomes [1,0,1,1,1,1] and we have 4 consecutive ones. The max number of consecutive ones is 4.
Constraints:
1 <= nums.length <= 10^{5}
nums[i]
is either0
or1
.
Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers coming from the stream as it's too large to hold in memory. Could you solve it efficiently?
Solutions
Suppose the problem statement allows for up to k
flips of zeroes to ones. In such scenarios, adopting a versatile solution becomes paramount for addressing this variant efficiently. The strategy involves maintaining a sliding window [left, right]
that encompasses at most k
zeroes. Here’s an enhanced explanation:

Sliding Window: Utilize a dynamic window
[left, right]
to traverse through the array. This window expands or contracts based on the condition related to zeroes within it. 
Handling Zeroes: As the window encounters a zero, increment a counter that tracks the number of zeroes (
zeroCount
). Subsequently, evaluate whetherzeroCount
exceedsk
. If
zeroCount
is greater thank
, it necessitates shifting theleft
boundary of the window to the right to exclude a zero and thereby maintain the constraint of at mostk
zeroes within the window. Should the element being excluded (nums[left]
) be a zero, decrementzeroCount
by one.  Conversely, if
zeroCount
does not exceedk
, leverage the current window size to potentially update the result (res
), signifying the maximum length of subarray achievable under the flipping constraint.
 If
Followup
In followup scenarios where direct access to prior elements via nums[left]
may not suffice or be efficient, an alternative approach is advocated:
 Zeroes Position Queue: Maintain a queue to record the positions of encountered zeroes. This queue becomes instrumental in precisely determining the next position to which the
left
boundary should shift when the window needs to exclude a zero to adhere to thek
flips constraint.
This queuebased approach ensures that adjustments to the window’s left
boundary are made with full knowledge of zeroes’ positions, thus optimizing window adjustments and maintaining the integrity of the k
flips constraint.
Summary
The refined solution not only caters to the basic requirement of flipping up to k
zeroes but also elegantly addresses more complex scenarios presented in followup questions. By systematically managing the sliding window and accurately tracking zeroes’ positions, this approach offers a robust and scalable solution to variants of the original problem.

class Solution { public int findMaxConsecutiveOnes(int[] nums) { int l = 0, r = 0; int k = 1; while (r < nums.length) { if (nums[r++] == 0) { k; } if (k < 0 && nums[l++] == 0) { ++k; } } return r  l; } }

class Solution { public: int findMaxConsecutiveOnes(vector<int>& nums) { int l = 0, r = 0; int k = 1; while (r < nums.size()) { if (nums[r++] == 0) { k; } if (k < 0 && nums[l++] == 0) { ++k; } } return r  l; } };

from collections import deque class Solution: def findMaxConsecutiveOnes(self, nums: List[int]) > int: res, zero, left, k = 0, 0, 0, 1 for right in range(len(nums)): if nums[right] == 0: zero += 1 while zero > k: if nums[left] == 0: zero = 1 left += 1 res = max(res, right  left + 1) # maxcheck every for iteration return res class Solution: # followup, extra space def findMaxConsecutiveOnes(self, nums: List[int]) > int: res, left, k = 0, 0, 1 q = deque() for right in range(len(nums)): if nums[right] == 0: q.append(right) if len(q) > k: left = q.popleft() + 1 res = max(res, right  left + 1) # maxcheck every for iteration return res ############ # maintain a sliding window of size 2, that keeps track of the counts. class Solution: # follow up, optimized def findMaxConsecutiveOnes(self, nums: List[int]) > int: count = 0 # Count of consecutive ones prev_count = 0 # Count of consecutive ones before a zero max_count = 0 # Maximum count of consecutive ones for num in nums: if num == 1: count += 1 prev_count += 1 else: count = prev_count + 1 prev_count = 0 max_count = max(max_count, count) # Reset the count and prev_count if we encounter two zeros in a row if num == 0 and prev_count == 0: count = 0 prev_count = 0 return max_count ############ class Solution: def findMaxConsecutiveOnes(self, nums: List[int]) > int: l = r = 0 k = 1 while r < len(nums): if nums[r] == 0: k = 1 if k < 0: if nums[l] == 0: k += 1 l += 1 r += 1 return r  l ############ class Solution(object): def __init__(self): self.ans = 0 self.count = 0 self.lastCount = 0 def findMaxConsecutiveOnes(self, nums): """ :type nums: List[int] :rtype: int """ for num in nums: self.readNum(num) # stream the input return self.ans def readNum(self, num): """ :type nums: int """ if num == 1: self.count += 1 else: self.count = self.count  self.lastCount + 1 self.lastCount = self.count self.ans = max(self.ans, self.count)

func findMaxConsecutiveOnes(nums []int) int { l, r := 0, 0 k := 1 for ; r < len(nums); r++ { if nums[r] == 0 { k } if k < 0 { if nums[l] == 0 { k++ } l++ } } return r  l }