How hard is LeetCode 1004. Max Consecutive Ones III?

LeetCode 1004. Max Consecutive Ones III is rated Medium on LeetCode.

What is the time complexity of LeetCode 1004. Max Consecutive Ones III?

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 1004. Max Consecutive Ones III?

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

What topics does LeetCode 1004. Max Consecutive Ones III cover?

LeetCode 1004. Max Consecutive Ones III is tagged Array, Binary Search, Prefix Sum and Sliding Window on LeetCode.

Max Consecutive Ones III — LeetCode 1004 Python Solution

MediumArrayBinary SearchPrefix SumSliding Window

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

The problem

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's.

Example

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]

Python solution

Python

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = cnt = 0
        for x in nums:
            cnt += x ^ 1
            if cnt > k:
                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 1004. Max Consecutive Ones III 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.

On a study list

This problem is on LeetCode 75.

Frequently asked questions

How hard is LeetCode 1004. Max Consecutive Ones III?: LeetCode 1004. Max Consecutive Ones III is rated Medium on LeetCode.
What is the time complexity of LeetCode 1004. Max Consecutive Ones III?: 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 1004. Max Consecutive Ones III?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1004. Max Consecutive Ones III cover?: LeetCode 1004. Max Consecutive Ones III is tagged Array, Binary Search, Prefix Sum and Sliding Window on LeetCode.