Is Max Consecutive Ones II easy or hard?

Max Consecutive Ones II is typically rated medium difficulty. The logic becomes straightforward once you recognize the sliding window pattern, but many candidates initially attempt slower brute force solutions before identifying the linear-time approach.

How to solve Max Consecutive Ones II in O(n)?

Use a sliding window that allows at most one zero in the current window. Expand the right pointer through the array and track how many zeros are inside the window. If the zero count exceeds one, move the left pointer forward until only one zero remains. The maximum window length encountered during the scan is the answer.

Max Consecutive Ones II Python or Java solution

In Python or Java, the implementation keeps two indices representing the window boundaries and a counter for zeros. Move the right pointer through the array, update the zero count, and shrink the window from the left when the zero limit is exceeded. This produces a clean O(n) implementation in both languages.

What is the best approach for Max Consecutive Ones II?

The sliding window approach is the most efficient and commonly expected solution. Maintain a window that contains at most one zero and expand it using two pointers. Whenever the zero count exceeds one, move the left pointer until the constraint is restored. This produces an O(n) time and O(1) space solution.

What data structure is used in Max Consecutive Ones II?

The core technique relies on the sliding window pattern with two pointers operating on an array. Only simple counters and indices are required, so no additional data structures like hash maps or stacks are needed for the optimal solution.

What is the time complexity of Max Consecutive Ones II?

The optimal solution runs in O(n) time because each element is processed at most twice by the sliding window pointers. Space complexity is O(1) since only a few counters and indices are maintained. Brute force approaches can take O(n^2) time due to repeated scans.

Is Max Consecutive Ones II asked at Google, Amazon, or Meta?

Variants of this problem appear frequently in interviews at companies like Amazon, Meta, and Google because it tests sliding window reasoning. Interviewers often extend it by allowing k flips instead of one or asking for the longest subarray with at most k zeros.

Description Solution Video 14:12

487. Max Consecutive Ones II

Medium52.0% acceptance4 companiesPremium elsewhere, free here

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⁵
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?