LeetCode 1004 - Max Consecutive Ones III

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Sliding Window, Prefix Sum

Solution

Problem Understanding

This problem asks us to find the length of the longest contiguous subarray that can contain only 1s after flipping at most k zeroes into ones.

The input consists of:

A binary array nums, where every element is either 0 or 1
An integer k, representing the maximum number of zeroes we are allowed to flip

The goal is to return the maximum size of a contiguous segment that can be transformed into all ones by changing no more than k zeroes.

For example, suppose we have:

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

We can flip one of the zeroes, which allows us to create a longer run of consecutive ones. The problem is asking for the maximum possible length after making such flips.

The constraints are important:

nums.length can be as large as 10^5
A quadratic solution would be too slow
We need something close to linear time

Since the array contains only binary values, we can think of the problem as maintaining a window where the number of zeroes does not exceed k.

Several edge cases are important:

k = 0, meaning no flips are allowed
The array contains only ones
The array contains only zeroes
k is larger than or equal to the number of zeroes in the array
Very small arrays such as length 1

A naive implementation can easily become inefficient if it repeatedly scans subarrays or recomputes zero counts.

Approaches

Brute Force Approach

The brute force solution considers every possible subarray.

For each starting index, we extend the ending index one step at a time and count how many zeroes appear inside the subarray. If the number of zeroes exceeds k, the subarray becomes invalid. Otherwise, we update the maximum length.

This approach is correct because it explicitly checks every contiguous segment and evaluates whether it can be converted into all ones with at most k flips.

However, there are O(n^2) possible subarrays, and counting or maintaining zeroes across all of them becomes too expensive for n = 10^5.

Optimal Sliding Window Approach

The key observation is that we only care whether the current window contains at most k zeroes.

If a window is valid, meaning it contains at most k zeroes, then every subarray inside it is also valid. This property makes the problem ideal for the sliding window technique.

We maintain two pointers:

left, the start of the window
right, the end of the window

As we expand the window to the right:

We count how many zeroes are inside
If the zero count exceeds k, we shrink the window from the left until it becomes valid again
At every step, we track the maximum valid window length

Each element enters and leaves the window at most once, giving an O(n) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every possible subarray
Optimal	O(n)	O(1)	Sliding window maintains at most `k` zeroes

Algorithm Walkthrough

Initialize two pointers, left = 0 and right = 0.

These pointers define the current sliding window. 2. Initialize a variable zero_count = 0.

This tracks how many zeroes exist inside the current window. 3. Initialize max_length = 0.

This stores the length of the longest valid window seen so far. 4. Iterate through the array using right.

At each step, include nums[right] into the window. 5. If nums[right] == 0, increment zero_count.

This reflects the fact that we would need one flip for this zero. 6. If zero_count > k, the window is invalid.

We now shrink the window from the left side until it becomes valid again. 7. While shrinking:

If nums[left] == 0, decrement zero_count
Increment left

This removes elements from the window one by one. 8. Once the window becomes valid again, compute its length:

window_length = right - left + 1

Update max_length if this window is larger than the previous best.
Continue until the entire array has been processed.

Why it works

The algorithm maintains the invariant that the current window always contains at most k zeroes.

Whenever the number of zeroes exceeds k, the left pointer moves forward until the constraint is restored. Since the window is always valid after adjustment, every recorded window length represents a feasible solution.

Because both pointers only move forward, every element is processed at most twice, once when entering the window and once when leaving it. This guarantees linear time complexity.

Python Solution

from typing import List

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0
        zero_count = 0
        max_length = 0

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

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

            current_length = right - left + 1
            max_length = max(max_length, current_length)

        return max_length

The implementation follows the sliding window strategy directly.

The variable left tracks the beginning of the current valid window, while the loop variable right expands the window one element at a time.

Whenever a zero is added into the window, zero_count increases. If the number of zeroes becomes larger than k, the window is no longer valid. The while loop shrinks the window from the left until the number of zeroes is once again acceptable.

After restoring validity, the current window length is calculated and compared with the best answer found so far.

The algorithm never revisits elements unnecessarily, which is why it achieves linear performance.

Go Solution

func longestOnes(nums []int, k int) int {
    left := 0
    zeroCount := 0
    maxLength := 0

    for right := 0; right < len(nums); right++ {
        if nums[right] == 0 {
            zeroCount++
        }

        for zeroCount > k {
            if nums[left] == 0 {
                zeroCount--
            }
            left++
        }

        currentLength := right - left + 1
        if currentLength > maxLength {
            maxLength = currentLength
        }
    }

    return maxLength
}

The Go implementation mirrors the Python version closely.

Go uses explicit variable declarations and standard for loops instead of Python's iterator syntax. Since all values fit comfortably within standard integer ranges, there are no integer overflow concerns.

Slices in Go already behave like dynamic array views, so no special handling is required for empty or nil slices beyond the normal logic.

Worked Examples

Example 1

Input:

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

Step	right	nums[right]	zero_count	left	Window	Length	max_length
1	0	1	0	0	[1]	1	1
2	1	1	0	0	[1,1]	2	2
3	2	1	0	0	[1,1,1]	3	3
4	3	0	1	0	[1,1,1,0]	4	4
5	4	0	2	0	[1,1,1,0,0]	5	5
6	5	0	3	move left	invalid	-	-

At this point, we shrink the window:

Remove index 0, still 3 zeroes
Remove index 1, still 3 zeroes
Remove index 2, still 3 zeroes
Remove index 3, now 2 zeroes

Now:

Step	right	left	Window	Length	max_length
6 continued	5	4	[0,0]	2	5

Continue expanding:

Step	right	nums[right]	zero_count	left	Length	max_length
7	6	1	2	4	3	5
8	7	1	2	4	4	5
9	8	1	2	4	5	5
10	9	1	2	4	6	6
11	10	0	3	shrink	-	6

Final answer:

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

The algorithm expands the window while keeping at most three zeroes inside.

The longest valid window becomes:

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

after flipping three zeroes.

The maximum length found is:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each pointer moves across the array at most once
Space	O(1)	Only a few variables are used

The sliding window guarantees linear time because every element is processed a constant number of times. The left and right pointers only move forward, never backward.

The algorithm uses constant extra memory because it stores only counters and indices, regardless of input size.

Test Cases

solution = Solution()

# Provided example 1
assert solution.longestOnes(
    [1,1,1,0,0,0,1,1,1,1,0], 2
) == 6

# Provided example 2
assert solution.longestOnes(
    [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], 3
) == 10

# Single element, already one
assert solution.longestOnes([1], 0) == 1

# Single element, flip allowed
assert solution.longestOnes([0], 1) == 1

# No flips allowed
assert solution.longestOnes([1,0,1,1,0,1], 0) == 2

# All ones
assert solution.longestOnes([1,1,1,1], 2) == 4

# All zeroes, enough flips
assert solution.longestOnes([0,0,0,0], 4) == 4

# All zeroes, partial flips
assert solution.longestOnes([0,0,0,0], 2) == 2

# k larger than number of zeroes
assert solution.longestOnes([1,0,1,1], 10) == 4

# Alternating pattern
assert solution.longestOnes([1,0,1,0,1,0,1], 2) == 5

# Long valid window at the end
assert solution.longestOnes([0,0,1,1,1,1], 1) == 5

# Long valid window at the beginning
assert solution.longestOnes([1,1,1,1,0,0], 1) == 5

Test	Why
Example 1	Verifies standard sliding window behavior
Example 2	Tests multiple shrink and expand operations
Single element one	Smallest valid input
Single element zero	Tests flip handling
`k = 0`	Ensures no flips are allowed
All ones	Entire array should be valid
All zeroes with enough flips	Entire array becomes valid
All zeroes with limited flips	Window size limited by `k`
Large `k`	Tests when every zero can be flipped
Alternating pattern	Frequent window adjustments
Long window at end	Ensures late maximum is found
Long window at beginning	Ensures early maximum is preserved

Edge Cases

One important edge case occurs when k = 0. In this situation, we are not allowed to flip any zeroes, so the problem becomes finding the longest existing run of ones. A buggy implementation might still allow invalid windows containing zeroes. This solution handles the case naturally because the window immediately shrinks whenever even one zero appears.

Another important case is when the array contains only zeroes. If k is smaller than the array length, the answer should simply be k, since we can only flip that many elements. The sliding window correctly limits the window size by shrinking whenever the number of zeroes exceeds k.

A third edge case happens when k is larger than the number of zeroes in the entire array. In that scenario, the whole array can be converted into ones. Some implementations incorrectly continue shrinking the window unnecessarily, but this algorithm never shrinks unless zero_count > k, so the full array length is returned correctly.

A subtle case involves very small arrays such as length 1. Off by one errors are common when computing window sizes. Using the formula:

right - left + 1

ensures the window length is calculated correctly even for single element windows.