Max Consecutive Ones III
Understanding the Problem
The problem talks about flipping zeros, but a reframing makes it easier to solve: we never need to decide which zeros to flip. We need 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 its length is a candidate answer, and the longest such subarray is the answer.
This turns the problem from "which zeros should I flip?" into finding the longest contiguous window that holds 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]is0or1→ Binary array, so a window only needs a single zero counter, no value bookkeeping.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
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 the answer.
For each starting index i, extend a subarray to the right while keeping a running count of zeros. Once the count exceeds k, stop extending (a longer subarray from the same start can only have more zeros) and move to the next starting index.
Algorithm
- Initialize
maxLen = 0 - For each starting index
ifrom0ton-1: - Initialize
zeroCount = 0 - For each ending index
jfromiton-1: - If
nums[j] == 0, incrementzeroCount - If
zeroCount > k, break (no point extending further) - Otherwise, update
maxLen = max(maxLen, j - i + 1) - Return
maxLen
Example Walkthrough
Code
- 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 every starting index re-scans the array from scratch. The next approach reuses the previous window instead of rebuilding it, which cuts the running time to linear.
Approach 2: Sliding Window
Intuition
Instead of restarting the scan for each starting position, maintain a window defined by two pointers, left and right. Expand the window by moving right forward. When the window holds more than k zeros, shrink from the left until it is valid again.
Removing an element from the left is cheap: when left advances past a zero, the zero count drops by one, so the count stays correct without recounting. Each element is added once (when right passes it) and removed at most once (when left passes it), which gives a linear-time algorithm.
The window is shrunk only when it has more than k zeros, and shrinking stops the moment it becomes valid again. So for every right, left sits at the smallest index for which [left, right] is valid, which makes right - left + 1 the longest valid window ending at right. Taking the maximum over all right covers every position where the longest window can end.
Algorithm
- Initialize
left = 0,zeroCount = 0,maxLen = 0 - For each
rightfrom0ton-1: - If
nums[right] == 0, incrementzeroCount - While
zeroCount > k: - If
nums[left] == 0, decrementzeroCount - Increment
left - Update
maxLen = max(maxLen, right - left + 1) - Return
maxLen
Example Walkthrough
Code
- Time Complexity: O(n). Each element is processed at most twice (once by
right, once byleft), so the total work is linear. - Space Complexity: O(1). Only a few integer variables used.
The sliding window is already O(n). The next approach drops the inner shrink loop entirely: instead of contracting the window when it becomes invalid, it slides the window forward at a fixed size. The result is the same answer with a single pointer move per step.
Approach 3: Sliding Window (Non-Shrinking)
Intuition
Once a valid window of size W exists, only a larger window can improve the answer. So instead of shrinking when the zero count exceeds k, slide the window: advance left once for each over-budget right, so both pointers move forward together and the size holds.
When right lands on a zero that pushes the count over k, move left forward by exactly one (not in a loop). If nums[left] was a zero, the 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 one zero over budget, so it keeps sliding at a fixed size until a future left-step removes a zero. Either way the size never shrinks.
The largest window ever reached is right - left + 1 at the end, which equals n - left.
left advances at most once per right, so right - left + 1 never decreases. The window can carry at most one extra zero (the step that pushed the count to k+1), and a valid window of the best size seen so far is always representable at the current width. So once the window reaches the optimal width, it never narrows below it, and the final width n - left equals the longest valid window in the array.
Algorithm
- Initialize
left = 0,zeroCount = 0 - For each
rightfrom0ton-1: - If
nums[right] == 0, incrementzeroCount - If
zeroCount > k: - If
nums[left] == 0, decrementzeroCount - Increment
left - Return
right - left + 1(which equalsn - left)
Example Walkthrough
Code
- Time Complexity: O(n). Single pass through the array. Unlike Approach 2, there's no inner while loop,
leftmoves at most once per iteration ofright. - Space Complexity: O(1). Only a few integer variables.