MediumNo. 1004

Max Consecutive Ones III — LeetCode 1004 Python Solution

Topics
Array, Binary Search, Prefix Sum, Sliding Window
On a study list
LeetCode 75
Reading time
2 min

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

PythonSolution
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

Time
O(n)where n is the length of the array
Space · auxiliary
O(1)

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.

Related problems

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.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.