How hard is LeetCode 487. Max Consecutive Ones II?

LeetCode 487. Max Consecutive Ones II is rated Medium on LeetCode.

What is the time complexity of LeetCode 487. Max Consecutive Ones II?

The Python solution on this page runs in O(n), where n is the length of the array.

What is the space complexity of LeetCode 487. Max Consecutive Ones II?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 487. Max Consecutive Ones II cover?

LeetCode 487. Max Consecutive Ones II is tagged Array, Dynamic Programming and Sliding Window on LeetCode.

Is LeetCode 487. Max Consecutive Ones II a premium problem?

Yes. LeetCode 487. Max Consecutive Ones II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Max Consecutive Ones II — LeetCode 487 Python Solution

MediumLeetCode PremiumArrayDynamic ProgrammingSliding Window

Problem: #487
Pattern: Sliding Window
Reading time: 2 min
Source: leetcode.com

The problem

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

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.

Python solution

Python

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        l = cnt = 0
        for x in nums:
            cnt += x ^ 1
            if cnt > 1:
                cnt -= nums[l] ^ 1
                l += 1
        return len(nums) - l

Complexity

Measure	Complexity
Time	O(n), where n is the length of the array
Space	O(1) auxiliary

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 487. Max Consecutive Ones II is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 487. Max Consecutive Ones II?: LeetCode 487. Max Consecutive Ones II is rated Medium on LeetCode.
What is the time complexity of LeetCode 487. Max Consecutive Ones II?: The Python solution on this page runs in O(n), where n is the length of the array.
What is the space complexity of LeetCode 487. Max Consecutive Ones II?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 487. Max Consecutive Ones II cover?: LeetCode 487. Max Consecutive Ones II is tagged Array, Dynamic Programming and Sliding Window on LeetCode.
Is LeetCode 487. Max Consecutive Ones II a premium problem?: Yes. LeetCode 487. Max Consecutive Ones II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.