Max Consecutive Ones III
Problem
nums and an integer k, you may turn
at most k zeros into ones. Return the length of the longest run of
consecutive ones you can achieve.nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2Output6nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3Output10nums = [0,0,0], k = 0Output01 ≤ n ≤ 105 · nums[i] is 0 or 1 · 0 ≤ k ≤ n
Try it yourself
class Solution {
public int longestOnes(int[] nums, int k) {
}
}
Instinct Longest, shortest or count of contiguous subarrays/substrings meeting a rule? Grow a window on the right, shrink it on the left, never step back.
Memory hack Move like a caterpillar - the head stretches forward to grab, the tail pulls up only when the body breaks the rule.
Open the Sliding Window guide →Approaches
Brute ForceExtend from Every Start
O(n2)Space O(1)For each start i, walk j rightwards counting zeros
and stop as soon as the count exceeds k. The last valid
j gives the longest flip-able run starting at i.
public int longestOnes(int[] nums, int k) { int n = nums.length, best = 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; // budget exceeded best = Math.max(best, j - i + 1); } } return best; }
Correct and tiny, but an all-ones array costs n2/2 steps.
BetterPrefix Zero Counts + Binary Search
O(n log n)Space O(n)Let pre[i] = zeros in nums[0..i-1]; it never
decreases. For each end r, the best start is the smallest
l with pre[r+1] - pre[l] ≤ k, found by binary search on
the sorted prefix array.
public int longestOnes(int[] nums, int k) { int n = nums.length, best = 0; int[] pre = new int[n + 1]; for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + (nums[i] == 0 ? 1 : 0); for (int r = 0; r < n; r++) { int need = pre[r + 1] - k; // want first l with pre[l] >= need int lo = 0, hi = r + 1; while (lo < hi) { int mid = (lo + hi) >>> 1; if (pre[mid] >= need) hi = mid; else lo = mid + 1; } best = Math.max(best, r - lo + 1); } return best; }
Faster than quadratic, but needs O(n) memory and a log factor.
OptimalSliding Window with Zero Budget
O(n)Space O(1)Expand right and count zeros inside the window. While the count
exceeds k, advance left (releasing a zero when one leaves).
Each index enters and leaves once, so the total work is linear.
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) { if (nums[left] == 0) zeros--; left++; } best = Math.max(best, right - left + 1); } return best; }
Dry runnums = [1,0,0,1,1,0,1], k = 1
- r=11l0r01101zeros 1, best 2
- r=2100l r1101zeros 2 → left=2
- r=4100l11r01zeros 1, best 3
- r=51001l10r1zeros 2 → left=3
- r=61001l101rbest 4 ✔
One pass, constant memory — the standard answer.
while with if and the window never shrinks;
the answer is then n - left.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Extend from Every Start | O(n2) | O(1) |
| Better | Prefix Zero Counts + Binary Search | O(n log n) | O(n) |
| Optimal | Sliding Window with Zero Budget | O(n) | O(1) |
- Trying to choose which zeros to flip — the window decides that implicitly.
- Decrementing
zeroswhen a1leaves the window. - Forgetting
k = 0: the answer is then the longest existing run of ones.
- Restate the problem as “longest subarray with at most k zeros” out loud.
- Argue O(n):
leftandrighteach move at most n times. - Link it to LC 424 — same window, different notion of “bad” element.