Max Consecutive Ones III | AlgoDrill Interview Course

Given a binary array nums and a non-negative integer k, return the longest contiguous run of ones obtainable by changing at most k zeroes to ones.

A window can be changed into all ones exactly when it contains at most k zeroes. Each zero requires one flip, while a one requires none, so the algorithm only needs to count the zeroes currently inside the window.

Move right across the array. When the new value is zero, increase zero_count.

If zero_count becomes larger than k, moving right farther cannot repair the window because expanding never removes any of the zeroes already inside it. Move left forward until enough zeroes leave and zero_count <= k again.

Moving past a one changes the window boundaries but does not free a flip, so zero_count stays unchanged. Moving past a zero reduces zero_count by one.

Which range uses at most two flips?

1 / 16

zero_count: 0
best_length: 1

Start with left and right at index 0. The window contains one 1, uses no flips, and sets best_length to 1.

When shrinking stops, left is the earliest remaining start whose window ending at right uses at most k flips. Any start already passed by left was ruled out when its window contained too many zeroes, and expanding farther right cannot make that earlier start valid again.

Only after the window is valid should its length be compared with best_length.

Why does the algorithm need only the number of zeroes in the window, rather than the positions of the zeroes it will flip?

In the implementation, zeros is the current zero_count, and res stores the best length found so far.

1class Solution:

2 def longestOnes(self, nums: list[int], k: int) -> int:

3 left = 0

4 zeros = 0

5 res = 0

7 for right, x in enumerate(nums):

8 if x == 0:

9 zeros += 1

11 while zeros > k:

12 if nums[left] == 0:

13 zeros -= 1

14 left += 1

16 res = max(res, right - left + 1)

18 return res

With k = 0, every zero makes the current range invalid until that zero leaves. The same loop finds the longest run already made entirely of ones.

Time: O(n)Space: O(1)

right visits each array position once, and left moves only forward across at most the same n positions. Total time is O(n). The boundaries, zero count, and best length use O(1) auxiliary space.