LeetCode 1004: Max Consecutive Ones III

Problem Restatement

We are given a binary array nums and an integer k.

We can flip at most k zeros to ones.

We need to return the maximum number of consecutive ones in the array after performing at most k flips.

The official constraints state that 1 <= nums.length <= 10^5, nums[i] is either 0 or 1, and 0 <= k <= nums.length.

Input and Output

Function shape:

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

Examples

Example 1:

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

Flip two zeros at indices 9 and 10:

[1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1]

But a better choice flips zeros at indices 3 and 4 or 9 and 10 to get:

The optimal window is from index 3 to 10, flipping two zeros.

Answer:

6

Example 2:

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

Flip zeros at indices 4, 5, and 9 to get a window of 10 ones.

Answer:

10

Key Insight

We want the longest window [left, right] that contains at most k zeros.

Use a sliding window:

• Expand the right end.
• If the window has more than k zeros, shrink the left end.
• Track the maximum window size.

Algorithm

1. Use two pointers left = 0 and right = 0.
2. Track zeros, the count of zeros in the current window.
3. For each right:
   • If nums[right] == 0, increment zeros.
   • While zeros > k, if nums[left] == 0, decrement zeros. Move left right.
   • Update the maximum length as right - left + 1.
4. Return the maximum length.

Correctness

At every step, the window [left, right] contains exactly zeros zeros.

When zeros > k, we shrink the left side until zeros <= k again.

Since both pointers only move right, each element is added and removed at most once.

The maximum window size found over all positions is the answer, because every valid window is considered.

Edge Cases

• Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
• Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
• When the target is absent, the loop should still terminate and return the problem-specific failure value.

Complexity

Common Pitfalls

• Do not mix inclusive and half-open bounds inside the same loop.
• Make sure each branch strictly reduces the search interval.

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

Code Explanation

We expand the window to the right:

for right in range(len(nums)):
    if nums[right] == 0:
        zeros += 1

When the zero count exceeds k, shrink from the left:

while zeros > k:
    if nums[left] == 0:
        zeros -= 1
    left += 1

After adjustment, the window is valid. Update the best:

best = max(best, right - left + 1)

Testing

def run_tests():
    s = Solution()

    assert s.longestOnes([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2) == 6
    assert s.longestOnes([0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], 3) == 10
    assert s.longestOnes([1, 1, 1], 0) == 3
    assert s.longestOnes([0, 0, 0], 0) == 0
    assert s.longestOnes([0, 0, 0], 3) == 3

    print("all tests passed")

run_tests()