medium Max Consecutive Ones III

Problem Statement

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

Examples

Example 1:

• Input: nums = [1, 0, 0, 1, 1, 0, 1, 1], k = 2
• Expected Output: 6
• Justification: By flipping 0 at the second and fifth index in the list, we get [1, 0, 1, 1, 1, 1, 1, 1], which has 6 consecutive 1s.

Example 2:

• Input: nums = [1, 0, 1, 1, 0, 0, 1, 1], k = 1
• Expected Output: 4
• Justification: By flipping 0 at the 1st index, we get [1, 1, 1, 1, 0, 0, 1, 1], with a maximum of 4 consecutive 1s (indices 0–3).

Example 3:

• Input: nums = [1, 0, 0, 1, 1, 0, 1], k = 3
• Expected Output: 7
• Justification: By flipping all three zeros, we get [1, 1, 1, 1, 1, 1, 1], which has 7 consecutive 1s.

Constraints:

• 1 <= nums.length <= 10⁵
• nums[i] is either 0 or 1.
• 0 <= k <= nums.length

Pattern

Variable window with flip budget k. Expand right always; while zeros in window > k, advance left. Answer = max valid length. Same family as "at most K distinct" and "delete one zero" (k=1 with length−1). Shrink must be a while. Edges: k=0 → longest pure-1 run; k ≥ zero-count → n.

Solution

Use a sliding window. Expand the right pointer as long as the number of 0s inside the window does not exceed k. When the count of 0s exceeds k, shrink the window from the left until it is valid again. The maximum valid window size is the answer.

This works because each 0 inside the window represents a flip we are "spending." The window always contains at most k flips, so its length is the longest consecutive run of 1s achievable with at most k flips.

Step-by-step Algorithm

1. Initialize left = 0, right = 0, max_length = 0, and zero_count = 0.
2. While right < nums.length:
   • If nums[right] == 0, increment zero_count.
   • While zero_count > k, shrink from the left: if nums[left] == 0, decrement zero_count; then increment left.
   • Update max_length = max(max_length, right - left + 1).
   • Increment right.
3. Return max_length.

Algorithm Walkthrough

For nums = [1, 0, 0, 1, 1, 0, 1, 1], k = 2:

1. right = 0: value 1, window [1], zero_count = 0, max_length = 1.
2. right = 1: value 0, zero_count = 1, window [1,0], max_length = 2.
3. right = 2: value 0, zero_count = 2, window [1,0,0], max_length = 3.
4. right = 3: value 1, window [1,0,0,1], max_length = 4.
5. right = 4: value 1, window [1,0,0,1,1], max_length = 5.
6. right = 5: value 0, zero_count = 3 > k. Shrink left: nums[0] = 1 (left becomes 1), nums[1] = 0 (zero_count becomes 2, left becomes 2). Window is now [0,1,1,0], max_length stays 5.
7. right = 6: value 1, window [0,1,1,0,1], max_length = 5.
8. right = 7: value 1, window [0,1,1,0,1,1], max_length = 6.

Diagram

The diagram below traces the sliding window as it expands and contracts over the array.

Index:  0  1  2  3  4  5  6  7
Array:  1  0  0  1  1  0  1  1
       [-------------]               (zeros = 2, length = 5)
          [----------------]          (zeros = 2, length = 6) ← answer

Code

class Solution {

  public int longestOnes(int[] nums, int k) {
    int left = 0, right = 0;
    int max_length = 0;
    int zero_count = 0;

    // Use sliding window to find the longest sequence of 1s with at most k 0s flipped
    while (right < nums.length) {
      // If current element is 0, increase zero_count
      if (nums[right] == 0) {
        zero_count++;
      }

      // If zero_count exceeds k, move left pointer to maintain at most k zeros in window
      while (zero_count > k) {
        if (nums[left] == 0) {
          zero_count--;
        }
        left++;
      }

      // Update max_length if current window is longer
      max_length = Math.max(max_length, right - left + 1);
      right++;
    }

    return max_length;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(
      sol.longestOnes(new int[] { 1, 0, 0, 1, 1, 0, 1, 1 }, 2)
    ); // 6
    System.out.println(
      sol.longestOnes(new int[] { 1, 0, 1, 1, 0, 0, 1, 1 }, 1)
    ); // 4
    System.out.println(sol.longestOnes(new int[] { 1, 0, 0, 1, 1, 0, 1 }, 3)); // 7
  }
}

Time Complexity

O(n) — each pointer traverses the array at most once.

Space Complexity

O(1) — only a few integer variables are used.

Try it yourself

Try solving this question on LeetCode.

Problem and solution structure adapted from DesignGurus. Re-authored for this guide.

Judgment layer — why this pattern, complexity derivation, when-NOT & drills

Why this exists (judgment layer)

At-most-k zeros in a window is the variable-window template with a budget resource — transferable to 'at most k distinct', 'longest with ≤k replacements', etc.

Worked example & complexity derivation

nums=[1,0,0,1,1,0,1,1], k=2
Expand right; while zeros>k advance left
… right=4 window zeros=2 len=5
right=5 third zero → shrink past index1 zero → zeros=2, window[2..5] len=4
right=7 → window[2..7]=[0,1,1,0,1,1] len=6 → answer 6
Each index enters/leaves at most once → O(n) time, O(1) space
Invariant: window always has ≤k zeros (valid flip set)

Pattern transfer & when-NOT

Pattern: VARIABLE WINDOW WITH FLIP BUDGET k. Family: Max Consecutive Ones III; Longest repeating char replacement; at most K distinct. When-NOT: exactly k zeros (adjust counting); must delete one even if no zero (see delete-one problem); 2D / non-contiguous → not this window. Shrink must be while not if.

Edge cases (hand-run)

k=0 → longest pure-1 run. k ≥ total zeros → answer n. All zeros with k=1 → 1. Empty not in constraints (n≥1).

Hostile-panel drills (defend the decision)

Q1. Why while (zeros>k) not if?
Model answer: One new zero can require advancing left past multiple zeros if the window already had k; for multi-unit shrinks while is the transferable habit. Here zeros increase by at most 1 per step so if often works, but while generalizes.

Q2. Relate to 'delete one zero' (k=1, length−1).
Model answer: Same window with k=1 zeros allowed; forced delete means answer is window_len−1 or track right-left without +1.

Q3. Complexity if k is huge?
Model answer: Still O(n) — k only affects how rarely left moves, not asymptotic passes.