Max Consecutive Ones III

Problem in Plain English

Given a binary array nums and an integer k, you may flip at most k zeros to ones. Return the length of the longest contiguous subarray that contains only ones after the flips.

Problem Statement

Given a binary array nums and an integer k, return the maximum number of consecutive 1s in the array if you can flip at most k 0s.

Flipping turns zeros into ones, so the task equals finding the longest contiguous subarray holding at most k zeros. For nums = [1,1,1,0,0,0,1,1,1,1,0] with k = 2 the answer is 6.

Constraints

1 <= nums.length <= 10^5
nums[i] is either 0 or 1.
0 <= k <= nums.length

Examples

Example 1

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6

Flip the zeros at indices 4 and 5 to get [1,1,1,0,1,1,1,1,1,1,0], whose longest run of ones has length 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

Flip the zeros at indices 4, 5 and 9 to get a run of 10 consecutive ones.

Example 3

Input: nums = [1,0,1,1,0], k = 0
Output: 2

No flips are allowed. The longest existing run is the two ones at indices 2 and 3.

Example 4

Input: nums = [0,0,0], k = 0
Output: 0

Every nonempty interval contains a zero and no flip is available, so no run of ones exists.

Example 5

Input: nums = [0,0,0], k = 2
Output: 2

Any two adjacent zeros can be flipped. Length 3 would need three flips, exceeding the budget.

Example 6

Input: nums = [1,0,1,0,1], k = 1
Output: 3

Either zero can be flipped to produce a run of length 3. Tied optimal windows are allowed; only the length is returned.

Intuition

Flipping at most k zeros means a candidate interval is usable exactly when it contains at most k zeros; ones cost nothing. In Example 1, indices 4 through 9 contain two zeros and four ones, giving length 6 after two flips. Track a window with a zero count. Extend its right edge, then remove values from its left until the zero budget is restored, keeping the longest valid length.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Every answer is some subarray, so we can test them all directly. From each start we extend right while counting zeros, and every extension within the budget of k zeros is a valid candidate.

Step-by-Step Logic

Initialize best = 0. For each start i, initialize zeros = 0 and extend end j from i toward the array end.
Add one to zeros whenever nums[j] is zero. If zeros > k, stop this start: every longer interval from i still includes those zeros.
For each valid extension, update best with j - i + 1. Example 1 extends start 0 through end 4 to length 5, then stops at end 5 when zeros reaches 3.
Repeat every later start. Start 4 reaches end 9 with exactly two zeros and length 6, improving best; other valid intervals tie or fall short.
Return the largest valid length, 6. If k = 0 and all values are zero, no extension is valid and best stays 0.

Why It Works

Every contiguous interval has a start i and an end j, and the loops examine every interval that can satisfy the zero budget. Once a start has more than k zeros, extending it cannot remove zeros, so early stopping excludes only invalid intervals. Validity is exactly the ability to flip every zero in that interval. best therefore records the maximum feasible length.

Dry Run

Brute Force: variable states at each step
Start i	End j	Added value	Zero count	Length	Action	Best after
0	0	1	0	1	valid: update maximum	1
0	1	1	0	2	valid: update maximum	2
0	2	1	0	3	valid: update maximum	3
0	3	0	1	4	valid: update maximum	4
0	4	0	2	5	valid: update maximum	5
0	5	0	3	6	budget exceeded: break	5
1	1	1	0	1	valid: update maximum	5
1	2	1	0	2	valid: update maximum	5
1	3	0	1	3	valid: update maximum	5
1	4	0	2	4	valid: update maximum	5
1	5	0	3	5	budget exceeded: break	5
2	2	1	0	1	valid: update maximum	5
2	3	0	1	2	valid: update maximum	5
2	4	0	2	3	valid: update maximum	5
2	5	0	3	4	budget exceeded: break	5
3	3	0	1	1	valid: update maximum	5
3	4	0	2	2	valid: update maximum	5
3	5	0	3	3	budget exceeded: break	5
4	4	0	1	1	valid: update maximum	5
4	5	0	2	2	valid: update maximum	5
4	6	1	2	3	valid: update maximum	5
4	7	1	2	4	valid: update maximum	5
4	8	1	2	5	valid: update maximum	5
4	9	1	2	6	valid: update maximum	6
4	10	0	3	7	budget exceeded: break	6
5	5	0	1	1	valid: update maximum	6
5	6	1	1	2	valid: update maximum	6
5	7	1	1	3	valid: update maximum	6
5	8	1	1	4	valid: update maximum	6
5	9	1	1	5	valid: update maximum	6
5	10	0	2	6	valid: update maximum	6
6	6	1	0	1	valid: update maximum	6
6	7	1	0	2	valid: update maximum	6
6	8	1	0	3	valid: update maximum	6
6	9	1	0	4	valid: update maximum	6
6	10	0	1	5	valid: update maximum	6
7	7	1	0	1	valid: update maximum	6
7	8	1	0	2	valid: update maximum	6
7	9	1	0	3	valid: update maximum	6
7	10	0	1	4	valid: update maximum	6
8	8	1	0	1	valid: update maximum	6
8	9	1	0	2	valid: update maximum	6
8	10	0	1	3	valid: update maximum	6
9	9	1	0	1	valid: update maximum	6
9	10	0	1	2	valid: update maximum	6
10	10	0	1	1	valid: update maximum	6
done	none	none	none	none	return	6

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

With n input values, each of n starts can scan to the end; an all-ones array performs n(n + 1)/2 extensions even with k = 0. Thus worst-case time is O(n^2), despite early breaks on some inputs. The start/end indices, zero count, and best use O(1) extra space, and the input is not changed.

Code

Solution.java

1class Solution {2    public int longestOnes(int[] nums, int k) {3        int best = 0;4        for (int i = 0; i < nums.length; i++) {5            int zeros = 0;6            for (int j = i; j < nums.length; j++) {7                if (nums[j] == 0) {8                    zeros++;9                }10                if (zeros > k) {11                    break;12                }13                if (j - i + 1 > best) {14                    best = j - i + 1;15                }16            }17        }18        return best;19    }20}

Hints

Hint 1

Restate the task: find the longest contiguous subarray containing at most k zeros.

Hint 2

Grow a window to the right and count the zeros inside it; the count only rises when a 0 enters.

Hint 3

When the zero count passes k, move the left edge forward until the count is back within budget, dropping a zero from the count each time one leaves.

Edge Cases

k = 0: no flip is allowed, so the answer is the longest existing run of ones.
k covers every zero, such as all zeros with k equal to the length: the whole array becomes ones and the answer is its length.
A single zero with k = 0 returns 0; with k = 1 it returns 1. A single one returns 1 regardless of k.

Common Mistakes and Interview Tips

Forgetting to decrement the zero count when a 0 leaves through the left edge, which freezes the window too small for the rest of the scan.
Resetting left to right on a violation instead of sliding it forward, which skips valid windows in between.
Using >= k as the shrink test instead of > k, which treats a window spending exactly the budget as invalid.
Updating best before restoring validity can record an interval containing too many zeros.
Interview tip: describe flips as a counted zero budget, explain why discarded starts stay invalid, and justify linear time by total pointer moves rather than loop nesting.

Key Takeaway

For the longest subarray under a counted budget, keep the count as running window state and shrink from the left only while the budget is exceeded.