#1004
Max Consecutive Ones III
Medium Variable window with budget
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
In a binary array you may flip at most k zeros to ones. Return the longest run of ones you can get.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: flip at most k zeros; longest run of ones?
Why this works: it's "longest window with at most k zeros". Count zeros in the window; shrink when there are too many.
Example: [1,1,1,0,0,0,1,1,1,1,0], k = 2
window can hold two 0sbest window [0,0,1,1,1,1] after sliding → length 6
✦Hints open one at a time
Rephrase: the longest window containing at most k zeros.
Count zeros in the window; shrink from the left when it exceeds k.
↗Approach
Expand right, counting zeros. While zeros > k, move left forward (decrementing zeros if a zero leaves). Track the window length.
</>Solution (Java)
class Solution {
public int longestOnes(int[] nums, int k) {
int left = 0, zeros = 0, best = 0;
for (int r = 0; r < nums.length; r++) {
if (nums[r] == 0) zeros++;
while (zeros > k) {
if (nums[left] == 0) zeros--;
left++;
}
best = Math.max(best, r - left + 1);
}
return best;
}
}!Common mistake
Actually flipping values in the array and trying to undo them — counting is enough.
Complexity
- Time: O(n).
- Space: O(1).
Topic: Sliding Window
🎬 Episode 10: video coming soon