Workspace

Problem workspace

3 day streakD

Max Consecutive Ones III

MediumSliding WindowLongest windows

The challenge

Return the longest contiguous run of ones obtainable by flipping at most k zeros in a binary array.

Every value is 0 or 1; k ≥ 0. The input is not modified.

Example

[1,1,1,0,0,0,1,1,1,1,0], k = 2 → 6.

Use the walkthrough below to inspect the input and each state change.

See Flip K zeros, step by step

Expand, shrink, and inspect the window state.

11 elements · zero-based indicesk = 2
Sliding window over 11 elementsThe current window is empty. Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.Empty window · L = 0, R = -110111203040516171819010
Current windowRecorded answerOutside window
Left
0
Right
-1
Length
0
Step 01 / 29

Start with an empty window

Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.

left = 0; right = −1

Answer so far

0
View exact input

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

Current window is empty.

Put it into code

Treat each zero as one unit of cost. Maintain a window whose zero count fits the flip budget.

Indices are zero-based. C++ uses C++17 or later.

def longest_ones(nums, k):
    left = zeros = best = 0
    for right, value in enumerate(nums):
        zeros += value == 0
        while zeros > k:
            zeros -= nums[left] == 0
            left += 1
        best = max(best, right - left + 1)
    return best

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap