Understanding the Problem

At first glance this looks like a problem about flipping zeros. But here's the reframing that makes it much easier to solve: we don't actually need to flip anything. Instead, we need to find the longest subarray that contains at most k zeros. Any subarray with at most k zeros can become all ones by flipping those zeros, so the length of that subarray is our answer.

This reframing turns the problem from "which zeros should I flip?" into a classic sliding window problem: find the longest contiguous window with at most k zeros.

Key Constraints:

nums.length <= 10^5 → We need O(n log n) or better. An O(n^2) brute force will likely TLE.
nums[i] is 0 or 1 → Binary array, so tracking zeros is simple (just count them).
0 <= k <= nums.length → k can be 0 (no flips allowed) or equal to the array length (flip everything). Both edge cases need handling.

Approach 1: Brute Force

Intuition

The most straightforward approach: check every possible subarray, count the zeros in it, and if the count is at most k, record its length. The longest such subarray is our answer.

For each starting index i, we extend a subarray to the right, keeping a running count of zeros. As soon as we exceed k zeros, we stop extending and move to the next starting index.

Algorithm

Initialize maxLen = 0
For each starting index i from 0 to n-1:

Initialize zeroCount = 0
For each ending index j from i to n-1:

If nums[j] == 0, increment zeroCount
If zeroCount > k, break (no point extending further)
Otherwise, update maxLen = max(maxLen, j - i + 1)

Return maxLen

Example Walkthrough

1i=0: expand j=0..4, zeros=2 at j=4, window=[1,1,1,0,0], maxLen=5

1/8

Code

Complexity Analysis

Time Complexity: O(n^2). For each of the n starting positions, we potentially scan up to n elements. The early break when zeros exceed k helps in practice, but worst case is still quadratic.
Space Complexity: O(1). We only use a few integer variables regardless of input size.

The bottleneck is that for every starting index, we re-scan the array from scratch. What if we could reuse the work from the previous window instead of starting over?

Approach 2: Sliding Window

Intuition

Instead of restarting the scan for each starting position, we maintain a window defined by two pointers — left and right. We expand the window by moving right forward, and when we've included too many zeros (more than k), we shrink from the left until the window is valid again.

The key insight: when we move left forward by one and that element was a zero, our zero count drops by one. So we can efficiently "undo" the effect of removing an element from the window. This way, each element is added once (when right passes over it) and removed at most once (when left passes over it), giving us an O(n) algorithm.

Why does this work?

Each element is visited at most twice — once when right moves over it, and once when left moves past it. The window always represents a valid subarray (at most k zeros), and we track the maximum valid window size seen so far. Because we only shrink when we have to, we're guaranteed to find the longest possible window.

Algorithm

Initialize left = 0, zeroCount = 0, maxLen = 0
For each right from 0 to n-1:

If nums[right] == 0, increment zeroCount
While zeroCount > k:

If nums[left] == 0, decrement zeroCount
Increment left
Update maxLen = max(maxLen, right - left + 1)

Return maxLen

Example Walkthrough

1right=0..2: all 1s, zeroCount=0, window grows to size 3

left

right

1/8

Code

Complexity Analysis

Time Complexity: O(n). Each element is processed at most twice (once by right, once by left), so the total work is linear.
Space Complexity: O(1). Only a few integer variables used.

The sliding window approach is already O(n), but notice that when the window shrinks, it can shrink all the way back. What if we designed a window that never shrinks, only slides forward?

Approach 3: Sliding Window (Non-Shrinking)

Intuition

Once we've found a valid window of size W, we only care about finding something larger. So instead of shrinking the window when we exceed k zeros, we just slide it — move both left and right forward by one. The window size stays the same or grows, but never decreases.

When right encounters a zero that pushes us over k, we move left forward by exactly one (not in a while loop). If nums[left] was a zero, the zero count drops back to k and the window is valid again at the same size. If nums[left] was a one, the window is still invalid, but that's fine — it'll just keep sliding until it becomes valid again at a larger or equal size.

The maximum window size we've ever achieved is simply right - left + 1 at the end.

Why does this work?

The window size right - left + 1 only increases or stays the same, never decreases. When the window is invalid (more than k zeros), both pointers move forward together, maintaining the current size. When the window is valid, only right moves, growing the window. So the final value of right - left + 1 (equivalently n - left) is the maximum valid window size we ever achieved.

Algorithm

Initialize left = 0, zeroCount = 0
For each right from 0 to n-1:

If nums[right] == 0, increment zeroCount
If zeroCount > k:

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

Return right - left + 1 (which equals n - left)

Example Walkthrough

1right=0..2: all 1s, zeroCount=0, window grows to size 3

left

right

1/9

Code

Complexity Analysis

Time Complexity: O(n). Single pass through the array. Unlike Approach 2, there's no inner while loop — left moves at most once per iteration of right.
Space Complexity: O(1). Only a few integer variables.

Max Consecutive Ones III

Understanding the Problem

Key Constraints:

Approach 1: Brute Force

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Sliding Window

Intuition

Algorithm

Example Walkthrough

Code

Approach 3: Sliding Window (Non-Shrinking)

Intuition

Algorithm

Example Walkthrough

Code

Get Premium