Max Consecutive Ones III
Description
Given a binary array nums (containing only 0s and 1s) and an integer k, find the maximum number of consecutive 1s you can achieve in the array if you are allowed to flip at most k zeros to ones.
You do not need to actually perform the flips — just determine the length of the longest contiguous subarray of 1s that would be possible after performing at most k flips.
Another way to think about it: find the longest subarray that contains at most k zeros, since each zero in that subarray would need exactly one flip to become a 1.
Examples
Example 1
Input: nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2
Output: 6
Explanation: By flipping the two zeros at indices 5 and 10, the array becomes [1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]. The longest consecutive block of 1s runs from index 5 through index 10, giving a length of 6. Alternatively, flipping zeros at indices 4 and 5 yields a block of six 1s from index 4 through index 9. Either way, the maximum achievable is 6.
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
Output: 10
Explanation: One optimal strategy is to flip the three zeros at indices 4, 5, and 9. After flipping, the subarray from index 2 through index 11 becomes all 1s, giving a consecutive run of length 10. No arrangement of three flips can produce a longer consecutive sequence.
Constraints
- 1 ≤ nums.length ≤ 10^5
- nums[i] is either 0 or 1
- 0 ≤ k ≤ nums.length
Editorial
Brute Force
Intuition
The most natural approach is to try every possible starting position in the array and see how far we can extend a window of consecutive 1s (including flipped zeros) from that position.
Imagine standing at the beginning of a hallway lined with light switches — some are on (1) and some are off (0). You are allowed to flip at most k switches from off to on. Starting at each position, you walk forward, flipping off-switches as you go, until you run out of flips. You record how far you walked, then go back and try the next starting position.
For each starting index i, we scan rightward with index j, counting the number of zeros we encounter. As long as the zero count does not exceed k, the subarray [i..j] is valid. Once we hit the (k+1)-th zero, we stop and record the length.
Step-by-Step Explanation
Let's trace through Example 1: nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2.
Step 1: Start from index i = 0, set zeros = 0. Begin scanning rightward.
Step 2: Scan j = 0, 1, 2 — all are 1s. zeros stays 0. Window covers [0..2], length = 3.
Step 3: j = 3, nums[3] = 0. Increment zeros to 1. Still within flip budget (1 ≤ 2). Window [0..3], length = 4.
Step 4: j = 4, nums[4] = 0. Increment zeros to 2. Exactly at the flip limit. Window [0..4], length = 5.
Step 5: j = 5, nums[5] = 0. zeros would become 3, exceeding k = 2. Stop here. Record length 5. Update max_length = 5.
Step 6: Starting positions i = 1, 2, 3 yield subarrays of length 4, 3, and 2 respectively — none beats 5.
Step 7: Start from i = 4, reset zeros = 0. j = 4: nums[4] = 0 (zeros = 1). j = 5: nums[5] = 0 (zeros = 2). Two flips consumed immediately.
Step 8: Expand j = 6, 7, 8, 9 — all are 1s. zeros stays at 2. Window [4..9], length = 6.
Step 9: j = 10, nums[10] = 0. zeros = 3 > k = 2. Stop. Record length 6 (indices 4 through 9). Update max_length = 6.
Step 10: Remaining starting positions (5 through 10) produce shorter subarrays.
Result: max_length = 6.
Brute Force — Trying Every Starting Position — Watch how the brute force fixes a starting position i, then scans rightward counting zeros until the flip budget is exceeded, recording the window length before moving to the next starting position.
Algorithm
- Initialize max_length = 0
- For each starting index i from 0 to n − 1:
a. Reset zeros = 0
b. For each ending index j from i to n − 1:- If nums[j] == 0, increment zeros
- If zeros > k, break out of the inner loop
- Update max_length = max(max_length, j − i + 1)
- Return max_length
Code
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n = nums.size();
int maxLength = 0;
for (int i = 0; i < n; i++) {
int zeros = 0;
for (int j = i; j < n; j++) {
if (nums[j] == 0) zeros++;
if (zeros > k) break;
maxLength = max(maxLength, j - i + 1);
}
}
return maxLength;
}
};class Solution:
def longestOnes(self, nums: list[int], k: int) -> int:
n = len(nums)
max_length = 0
for i in range(n):
zeros = 0
for j in range(i, n):
if nums[j] == 0:
zeros += 1
if zeros > k:
break
max_length = max(max_length, j - i + 1)
return max_lengthclass Solution {
public int longestOnes(int[] nums, int k) {
int n = nums.length;
int maxLength = 0;
for (int i = 0; i < n; i++) {
int zeros = 0;
for (int j = i; j < n; j++) {
if (nums[j] == 0) zeros++;
if (zeros > k) break;
maxLength = Math.max(maxLength, j - i + 1);
}
}
return maxLength;
}
}Complexity Analysis
Time Complexity: O(n²)
The outer loop iterates over all n starting positions. For each starting position, the inner loop can scan up to n elements in the worst case. This gives n × n = O(n²) total operations. For example, when k equals n (all zeros can be flipped), every inner loop scans the entire remaining array.
Space Complexity: O(1)
We only use a few integer variables (zeros, maxLength, loop indices). No additional data structures are needed, so the space usage is constant regardless of input size.
Why This Approach Is Not Efficient
With n up to 10^5, the brute force performs up to 10^10 operations in the worst case — far exceeding typical time limits of ~10^8 operations per second.
The fundamental inefficiency lies in redundant work. When we finish scanning from starting position i and move to i+1, we throw away everything we learned and start the scan from scratch. But notice a crucial property: if the window [i..j] is valid (contains at most k zeros), then as we move i rightward to i+1, the farthest valid j can only stay the same or move rightward — it never moves backwards.
This monotonicity means we never need to re-scan elements. Instead of restarting, we can maintain a sliding window that expands from the right and shrinks from the left. Each element is visited at most twice (once when entering the window, once when leaving), giving us O(n) instead of O(n²).
Optimal Approach - Sliding Window
Intuition
Instead of restarting the scan for each new starting position, we maintain a flexible window [left, right] that slides across the array. The window always satisfies one invariant: it contains at most k zeros.
Think of it like a stretchy rubber band placed over the array. You stretch the right end forward to include more elements. Whenever you stretch past too many zeros (more than k), you pull the left end forward to release some elements — specifically, you keep pulling until you release a zero, which brings the count back within budget.
The key insight is that both left and right pointers only move forward — they never go backwards. This means each element is processed at most twice (once when right reaches it, once when left passes it), giving us a total of O(n) work.
The answer is the maximum value of (right − left + 1) observed at any point during the traversal.
Step-by-Step Explanation
Let's trace through Example 1: nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2.
Step 1: Expand right to index 0. nums[0] = 1, not a zero. Window [0..0], zeros = 0, length = 1. max_length = 1.
Step 2: Expand right to index 1. nums[1] = 1. Window [0..1], zeros = 0, length = 2. max_length = 2.
Step 3: Expand right to index 2. nums[2] = 1. Window [0..2], zeros = 0, length = 3. max_length = 3.
Step 4: Expand right to index 3. nums[3] = 0 — first zero! zeros = 1 (within budget). Window [0..3], length = 4. max_length = 4.
Step 5: Expand right to index 4. nums[4] = 0 — second zero. zeros = 2, equals k. Flip budget exhausted. Window [0..4], length = 5. max_length = 5.
Step 6: Expand right to index 5. nums[5] = 0 — third zero! zeros = 3 > k = 2. Window is now invalid. We must shrink from the left.
Step 7: Shrink: move left past indices 0, 1, 2 (all 1s — removing them does not reduce the zero count). left = 3. zeros still 3.
Step 8: Shrink past index 3: nums[3] = 0, so removing it drops zeros to 2. left = 4. Window [4..5] is valid again, length = 2. max_length stays 5.
Step 9: Expand right to index 6. nums[6] = 1. Window [4..6], length = 3. max_length = 5.
Step 10: Expand right through indices 7 and 8 (both 1s). Window [4..8], length = 5. max_length = 5.
Step 11: Expand right to index 9. nums[9] = 1. Window [4..9], length = 6. max_length = 6! New best found.
Step 12: Expand right to index 10. nums[10] = 0 — zeros = 3 > k. Shrink: nums[left=4] = 0, remove it, zeros drops to 2. left = 5. Window [5..10], length = 6. max_length stays 6.
Step 13: All elements processed. max_length = 6.
Sliding Window — Expand and Shrink to Maximize Consecutive Ones — Watch the sliding window expand rightward to include elements and shrink leftward when the zero count exceeds k, always tracking the longest valid window.
Algorithm
- Initialize left = 0, zeros = 0, max_length = 0
- For each right from 0 to n − 1:
a. If nums[right] == 0, increment zeros
b. While zeros > k:- If nums[left] == 0, decrement zeros
- Increment left
c. Update max_length = max(max_length, right − left + 1)
- Return max_length
Code
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left = 0, zeros = 0, maxLength = 0;
for (int right = 0; right < nums.size(); right++) {
if (nums[right] == 0) zeros++;
while (zeros > k) {
if (nums[left] == 0) zeros--;
left++;
}
maxLength = max(maxLength, right - left + 1);
}
return maxLength;
}
};class Solution:
def longestOnes(self, nums: list[int], k: int) -> int:
left = 0
zeros = 0
max_length = 0
for right in range(len(nums)):
if nums[right] == 0:
zeros += 1
while zeros > k:
if nums[left] == 0:
zeros -= 1
left += 1
max_length = max(max_length, right - left + 1)
return max_lengthclass Solution {
public int longestOnes(int[] nums, int k) {
int left = 0, zeros = 0, maxLength = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) zeros++;
while (zeros > k) {
if (nums[left] == 0) zeros--;
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}Complexity Analysis
Time Complexity: O(n)
Although there is a while loop nested inside the for loop, the total work is still linear. The key observation is that the left pointer only moves forward and each element can be "left-passed" at most once. The right pointer visits each element exactly once, and the left pointer visits each element at most once. So the total number of pointer movements is at most 2n, which simplifies to O(n).
Space Complexity: O(1)
We use only a fixed number of integer variables (left, zeros, maxLength) regardless of the input size. No additional data structures are needed.