Max Consecutive Ones III (LC 1004)

Pattern: Sliding Window (at most k zeros inside the window)
Difficulty: Medium
Key Concept: Expand the right edge of the window; track how many zeros are inside; when zeros exceed k, shrink from the left until valid again. The maximum window length is the answer.

Problem Statement

Given a binary array nums (each element is 0 or 1) and an integer k, you may flip at most k values from 0 to 1.

Return the maximum number of consecutive 1s in the array after flipping at most k zeros (i.e., the maximum length of a subarray that contains at most k zeros, treating those zeros as flipped).

Input

nums: int[] with values in {0, 1}
k: int — maximum number of zeros allowed in the window

Output

int — maximum length of a valid contiguous subarray

1. Algorithm & Pseudocode

Brute force (try every start)

maxLen = 0
for left from 0 to n-1:
    zeros = 0
    for right from left to n-1:
        if nums[right] == 0:
            zeros++
        if zeros > k:
            break
        maxLen = max(maxLen, right - left + 1)
return maxLen

Optimal (sliding window)

Maintain [left, right] such that the count of zeros inside is ≤ k.

left = 0
zeros = 0
maxLen = 0
for right from 0 to n-1:
    if nums[right] == 0:
        zeros++
    while zeros > k:
        if nums[left] == 0:
            zeros--
        left++
    maxLen = max(maxLen, right - left + 1)
return maxLen

2. Step-by-Step Analysis (Beginner-Friendly)

Flips as “free” zeros
Instead of modifying the array, imagine you may include up to k zeros inside your window. Every zero “uses one flip.” When you exceed k, the window is invalid until you drop a zero from the left.
Why sliding window works
For a fixed right, if a window [left, right] is valid, any left' > left gives a shorter window. If you want the longest valid window ending at right, you only need the smallest left such that zeros in [left, right] ≤ k. Moving left right shrinks the zero count when you leave a zero behind.
Monotone left
left never moves backward across the array, so total work is linear even with an inner while.
Binary array as int[]
In Java, nums[i] is 0 or 1 as int. No separate boolean array is required—just compare to 0.
maxLen update timing
After ensuring zeros <= k, every valid [left, right] is a candidate; update maxLen with right - left + 1.

3. The Dry Run

Sample: nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2 (at most two zeros in the window)

We trace left, right, zeros after counting nums[right], then each while zeros > k shrink (showing left and zeros after each left++), then maxLen.

Step	`right`	`nums[right]`	`zeros` (after `if 0`)	Shrink (`while zeros > k`)	`left` after	window len	`maxLen`
1	0	1	0	—	0	1	1
2	1	1	0	—	0	2	2
3	2	1	0	—	0	3	3
4	3	0	1	—	0	4	4
5	4	0	2	—	0	5	5
6	5	0	3	`l=0` (1): `l=1`; `l=1` (1): `l=2`; `l=2` (1): `l=3`; `l=3` (0): `zeros=2`, `l=4`	4	2	5
7	6	1	2	—	4	3	5
8	7	1	2	—	4	4	5
9	8	1	2	—	4	5	5
10	9	1	2	—	4	6	6
11	10	0	3	`l=4` (0): `zeros=2`, `l=5`; `l=5` (0): `zeros=1`, `l=6`	6	5	6

Check: After step 10, window indices 4..9 are [0, 0, 1, 1, 1, 1] — exactly two zeros, length 6. After step 11, the best window ending at 10 is shorter, so maxLen stays 6.

Result: maxLen = 6.

4. Java Solution

Brute Force

class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int maxLen = 0;

        for (int left = 0; left < n; left++) {
            int zeros = 0;
            for (int right = left; right < n; right++) {
                if (nums[right] == 0) {
                    zeros++;
                }
                if (zeros > k) {
                    break;
                }
                maxLen = Math.max(maxLen, right - left + 1);
            }
        }

        return maxLen;
    }
}

Time: O(n²).
Space: O(1).

Optimal

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0;
        int zeros = 0;
        int maxLen = 0;

        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) {
                zeros++;
            }
            while (zeros > k) {
                if (nums[left] == 0) {
                    zeros--;
                }
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

Time: O(n) — each index visited by left and right at most once.
Space: O(1).

5. The “Java vs. Others” Edge

int[] for bits: Java uses int 0/1; simple and clear. C++ vector<bool> is a packed, proxy-based specialization (not a normal vector of bools)—iterator/reference surprises show up in generic code. Plain vector<int> or string of '0'/'1' is often preferred for clarity, similar to Java’s int[].
No bool in arithmetic: You compare nums[right] == 0 explicitly; Java does not treat nonzero ints as true.
Contrast Python: Python might use a list of ints too; boolean True/False are subclasses of int, but LeetCode inputs are still typically 0/1 integers—stay consistent with problem types.

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n²)	O(1)	Every `(left, right)` pair in worst case.
Optimal	O(n)	O(1)	Two pointers; `zeros` tracks flips used in the window.