#1004 Max Consecutive Ones III
the problem
In plain words
nums holds only 0s and 1s. You may turn up to k of the 0s into 1s. How long can the longest unbroken run of 1s become?
in nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
out 6
Flip the 0s at indices 5 and 10: nums[5..10] becomes six 1s in a row.
in nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
out 10
- 1 ≤ n ≤ 10⁵
- nums[i] is 0 or 1
- 0 ≤ k ≤ n
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSliding window (variable size)
Reword it: "find the longest window containing at most k zeros". Flipping is just a story — you never actually change the array.
solutions
From brute force to optimal
From each start, extend while the zero count stays ≤ k.
- For each i: zeros = 0.
- Extend j; count zeros; stop when zeros > k.
- Record the longest run.
Up to n extensions from each of n starts.
One counter.
class Solution { public int longestOnes(int[] nums, int k) { int best = 0; for (int i = 0; i < nums.length; i++) { int zeros = 0; for (int j = i; j < nums.length; j++) { if (nums[j] == 0) zeros++; if (zeros > k) break; // would need too many flips best = Math.max(best, j - i + 1); } } return best; }}Grow right; while zeros > k, shrink left; record the longest valid window.
- zeros = 0, left = 0.
- If nums[right] == 0, zeros++.
- While zeros > k: if nums[left] == 0, zeros--; left++.
- best = max(best, right − left + 1).
Each index enters and leaves the window at most once.
Three integers.
class Solution { public int longestOnes(int[] nums, int k) { int left = 0, zeros = 0, best = 0; for (int right = 0; right < nums.length; right++) { if (nums[right] == 0) zeros++; while (zeros > k) { // too many zeros to flip if (nums[left] == 0) zeros--; left++; } best = Math.max(best, right - left + 1); } return best; }}Dry run
in the room
How to say it in the interview
talk track
- Reword the problem first — interviewers (Meta especially) often disguise it, e.g. "work days and k leave days: longest streak off".
- Note it is the binary version of LC 424.
traps
- Actually flipping values in the array — unnecessary and it breaks the shrink step.
what they ask next
Follow-ups
Max Consecutive Ones II (LC 487): k = 1, and the input is a stream?
Same window with k = 1; for a stream, store only the index of the last zero instead of the whole array.
before you submit
Edge cases to test
- k = 0: the answer is the longest run of ones already there.
- k ≥ number of zeros: the whole array.
- All zeros with k = 0 → 0.
- Never actually flip values in the array — just count the zeros in the window.
practise next
Similar problems
- #424Longest Repeating Character ReplacementMediumin Sliding Window
- #3Longest Substring Without Repeating CharactersMediumin Sliding Window
- #209Minimum Size Subarray SumMediumin Sliding Window