MediumArrayBinary SearchSliding WindowPrefix Sum

Max Consecutive Ones III

1 approach, code in every language

You are given a binary array nums containing only 0s and 1s, together with an integer k. You may flip at most k of the zeros into ones.

Return the length of the longest contiguous run of ones you can obtain after performing those flips optimally.

Equivalently, find the longest subarray that contains no more than k zeros, since those zeros are exactly the ones you would flip.

Example 1

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2

Output: 6

Flipping two of the zeros in the middle yields the run [1,1,1,0,0,1,1,1,1] trimmed to a window of six consecutive ones.

Example 2

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3

Output: 10

A window covering ten positions can be made all ones by flipping at most three zeros inside it.

Constraints

1 <= nums.length <= 10^5
nums[i] is either 0 or 1.
0 <= k <= nums.length

Sliding Window With a Zero Budget

Grow a window while tracking how many zeros it contains; whenever the zero count exceeds k, advance the left edge until the budget is restored.

Loading animation…

Intuition

Since flipping a zero is what costs us, a window is achievable exactly when it holds at most k zeros. We slide a right pointer forward and count the zeros currently inside the window. As long as that count stays within k the window is feasible and we can extend it. When adding a new zero pushes the count above k, we advance the left pointer, discarding elements until we have dropped one zero and are back within budget. The widest window we ever observe is the answer, and because both pointers only move forward the algorithm is linear.

Algorithm walkthrough

1Initialize left at 0, a zeros counter at 0, and best at 0.
2Move the right pointer across the array; each time nums[right] is 0, increment zeros.
3If zeros exceeds k, shrink from the left: while the count is too high, if nums[left] is 0 decrement zeros, then advance left.
4After restoring the budget, the window from left to right contains at most k zeros and is therefore achievable.
5Update best with the current window width right - left + 1.
6When the right pointer finishes, return best.

Implementation

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0
        zeros = 0
        best = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                zeros += 1
            while zeros > k:
                if nums[left] == 0:
                    zeros -= 1
                left += 1
            best = max(best, right - left + 1)
        return best

Time

O(n)

Space

O(1)

Both the left and right pointers move forward at most n times, and only a few scalars are stored.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Longest Verified Backup Streak is our own problem on the technique behind Max Consecutive Ones III: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free