Sliding Window — Max Consecutive Ones III
↗ LeetCode: Max Consecutive Ones III · Medium · pattern chapter →
Given a binary array nums and integer k, return the maximum length of a subarray containing only 1s after flipping at most k zeros.
Example 1 — nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 → 6 (flip the two zeros in the middle group; window [1,1,1,0,0,1,1,1,1] — no wait — final window [1,1,1,0,0,1,1,1]after flipping the middle 0s gives 6 in one run) **Example 2** —nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3→10**Example 3** —nums = [1,1,1,1], k = 0→4`
Constraints — 1 ≤ n ≤ 10⁵; nums[i] ∈ {0, 1}; 0 ≤ k ≤ n. Brute expands every window in O(n²) = 10¹⁰ ops at n=10⁵ (TLE). Sliding window with k-tolerance stays O(n) = 10⁵ ops.
Interview timer00:00
Approach 1 — Try every subarray
Intuition. For each [i, j], count zeros; if zeros ≤ k, track length.
int longestOnesBrute(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) best = Math.max(best, j - i + 1);
else break;
}
}
return best;
}Complexity — Time O(n²); Space O(1).
Approach 2 — Sliding window with zero counter
Insight from brute. Growing right never decreases the zero count. Once we exceed k, we must shrink left past a zero to reduce it.
int longestOnesSlide(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--;
best = Math.max(best, right - left + 1);
}
return best;
}Complexity — Time O(n) — each index enters/leaves window once; Space O(1).
Approach 3 — Non-shrinking window (interview polish)
Insight from sliding. For a maximum-length answer, we never need to shrink below best. We can keep the window size monotonic non-decreasing.
int longestOnes(int[] nums, int k) {
int left = 0, zeros = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) zeros++;
if (zeros > k) { if (nums[left] == 0) zeros--; left++; }
}
return nums.length - left;
}Complexity — Time O(n); Space O(1). Same asymptotics, one less inner loop.
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Every subarray | O(n²) | O(1) | baseline |
| Sliding window + zero counter | O(n) | O(1) | expected optimum |
| Non-shrinking window | O(n) | O(1) | polish — one-pass, no inner while |
When to use which
- First pass — state brute, then jump to sliding-window with zero counter.
- "Max length" only → prefer non-shrinking version.
- "Return the window itself" → keep the shrinking version and track
(bestL, bestLen). - "Flip 1s to 0s instead" → complementary problem — swap semantics.
Related problems
- Longest Subarray of 1s After Deleting One Element —
k=1with deletion - Longest Repeating Character Replacement — generalization to arbitrary alphabet
- Fruit Into Baskets —
k=2distinct - Longest Substring with At Most K Distinct Characters