487

487. Max Consecutive Ones II (Medium)

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 <= 105
• nums[i] is either 0 or 1.

 

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?

Companies: Yandex, Google, TikTok, Zoom

Related Topics:
Array, Dynamic Programming, Sliding Window

Similar Questions:

• Max Consecutive Ones (Easy)
• Max Consecutive Ones III (Medium)
• All Divisions With the Highest Score of a Binary Array (Medium)

Solution 1. Sliding Window

Check out "C++ Maximum Sliding Window Cheatsheet Template!".

Shrinkable Sliding Window:

// OJ: https://leetcode.com/problems/max-consecutive-ones-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& A) {
        int zero = 0, i = 0, j = 0, N = A.size(), ans = 0;
        while (j < N) {
            zero += A[j++] == 0;
            while (zero > 1) zero -= A[i++] == 0;
            ans = max(ans, j - i);
        }
        return ans;
    }
};

Non-shrinkable Sliding Window:

// OJ: https://leetcode.com/problems/max-consecutive-ones-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& A) {
        int zero = 0, i = 0, j = 0, N = A.size();
        while (j < N) {
            zero += A[j++] == 0;
            if (zero > 1) zero -= A[i++] == 0;
        }
        return j - i;
    }
};

Discuss

https://leetcode.com/problems/max-consecutive-ones-ii/discuss/1499844/C%2B%2B-Sliding-Window-(%2B-Cheat-Sheet)