Skip to main content

Max Consecutive Ones III

— Prerna Sharma

Max Consecutive Ones III

Max Consecutive Ones III – LeetCode #1004 | DSA for Beginners

Brute force all subarrays → Variable-size Sliding Window. Master the "shrink when invalid" pattern.

Medium Sliding Window Array Two Pointers

Problem Statement

Given

A binary array nums (containing only 0s and 1s) and an integer k. Return the maximum number of consecutive 1s in the array if you can flip at most k zeros to ones.

Examples

Example 1
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: Flip the 0s at index 3 and 10 → [1,1,1,1,0,0,1,1,1,1,1]. Wait — the optimal is flipping indices 3 and 5 isn’t contiguous. The best is flipping indices 9 and 10: [1,1,1,0,0,0,1,1,1,1,1] → 5, or indices 3 and 4: [1,1,1,1,1,0,1,1,1,1,0] → 5. Actually the answer of 6 comes from flipping indices 9 and 10: subarray [1,1,1,1,1,1] at positions 5–10 after optimal flips. The window [idx 4..9]: 0,0,1,1,1,1 with 2 flips → 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
Explanation: Flip 3 zeros at positions 4, 5, 9 → window of length 10.

Constraints: 1 ≤ nums.length ≤ 105  •  nums[i] is 0 or 1  •  0 ≤ k ≤ nums.length

The Key Mental Shift 🧠

The problem says "flip at most k zeros to ones." But instead of thinking about flipping, reframe it as:

"Find the longest subarray that contains at most k zeros"

Every 0 inside the window is a flip we’re using. As long as zero-count ≤ k, the window is valid and all those zeros could be flipped.

This makes it a classic variable-size sliding window: expand the right end, and when the window becomes invalid (zeros > k), shrink from the left until it’s valid again.

nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2  —  best window (indices 5–10, length 6):

1 (no flip needed)
0 (flipped to 1)
outside window
1
0
1
1
1
2
0
3
0
4
0
5
flip
1
6
1
7
1
8
1
9
0
10
flip

Window [5..10] = [0,1,1,1,1,0] with 2 flips → length 6 ✅

Approaches at a Glance

🐌 Brute Force (All Subarrays)

Try every possible start and end pair. Count zeros in each window. Track the longest valid one.

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

⚡ Variable Sliding Window (Optimal)

Expand right freely. When zeros exceed k, shrink left until valid. One pass, O(n).

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

Fixed Window vs Variable Window — What’s Different?

Fixed-size (e.g. LC #643)

Window size is always exactly k. After reaching size k, always shrink by 1 from the left on every step.

Variable-size (this problem)

Window can grow or shrink. Shrink only when the window becomes invalid (zeros > k). Window size fluctuates.

Approach 1 — Brute Force (All Subarrays)

Try every possible subarray by fixing a start index i and expanding the end index j. Count zeros as we expand. If zeros ≤ k, this window is valid — update the max length. If zeros exceed k, break (further expanding will only add more zeros).

  • Outer loop: i from 0 to n−1 — each starting position.
  • Reset zeros = 0 for each new start.
  • Inner loop: j from i to n−1 — expand end of window.
  • If nums[j] == 0, increment zero count. If zeros > k, break early.
  • Otherwise update maxLen = max(maxLen, j − i + 1).


  
  
🔍 Dry Run — Brute Force

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

  
Showing only key rows (n=11, many iterations omitted for brevity):


  

    
      
i (start)j (end)nums[j]zeroszeros ≤ k?window lenmaxLen

    
    
      
0010✅ yes11

      
0110✅ yes22

      
0210✅ yes33

      
0301✅ yes44

      
0402✅ yes55

      
0503❌ no—5 (break)

      
… i=1,2,3,4 all yield maxLen ≤ 5 …

      
5501✅ yes15

      
5611✅ yes25

      
5711✅ yes35

      
5811✅ yes45

      
5911✅ yes55

      
51002✅ yes66 ↑ BEST!

      
… remaining start positions yield maxLen ≤ 6 …

    
  


  

    ⚠️ Why this is slow: For n=100,000, the worst case (all 1s, k=n) checks n²/2 = 5 billion pairs. Each inner loop re-counts zeros from scratch for every new start index. We’re doing repeated redundant work — sliding window eliminates this entirely.
  


  
  
Approach 2 — Variable Sliding Window (Optimal) ⚡


  
Intuition — Expand Greedily, Shrink When Forced

  
Instead of restarting from scratch for each i, maintain a window [windowStart, windowEnd] and track how many zeros are inside it.

  
    
    
  • Always expand: Move windowEnd right by 1. If nums[windowEnd] == 0, increment zeros.
    • 
    
  • Shrink if invalid: While zeros > k, move windowStart right. If the element leaving is 0, decrement zeros.
    • 
    
  • Record: After shrinking, the window [windowStart, windowEnd] is valid. Update maxLength.
    • 
  


  

    
Why the while loop (not if)?

    
When a single new zero tips zeros over k, we might need to move windowStart past multiple ones before we reach and expel the oldest zero. A while loop keeps shrinking until the window is valid again.

  


  
  
🔍 Dry Run — Sliding Window (Detailed)

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

  
S = windowStart  ↑  E = windowEnd  ↑


  

    
1 in window

    
0 in window (flip used)

    
windowStart

    
outside window

  


  
  

    

      E=0,1,2
      All 1s — zeros=0, window grows freely
    

    

      
1
0 ↑S,E

      
1
1

      
1
2

      
0
3

      
0
4

      
0
5

      
1
6

      
1
7

      
1
8

      
1
9

      
0
10

    

    
After E=2: zeros=0 ≤ 2 • window=[0..2] • maxLength = max(0, 3) = 3

  


  
  

    

      E=3
      First zero encountered — 1 flip used
    

    

      
1
0 ↑S

      
1
1

      
1
2

      
0
3 ↑E

      
0
4

      
0
5

      
1
6

      
1
7

      
1
8

      
1
9

      
0
10

    

    
nums[3]=0 → zeros=1 ≤ 2 • window=[0..3] • maxLength = max(3, 4) = 4

  


  
  

    

      E=4
      Second zero — 2 flips used, still valid
    

    

      
1
0 ↑S

      
1
1

      
1
2

      
0
3

      
0
4 ↑E

      
0
5

      
1
6

      
1
7

      
1
8

      
1
9

      
0
10

    

    
nums[4]=0 → zeros=2 ≤ 2 • window=[0..4] • maxLength = max(4, 5) = 5

  


  
  

    

      E=5 — INVALID! zeros=3 > k=2
    

    

      
1
0 ↑S

      
1
1

      
1
2

      
0
3

      
0
4

      
0
5 ↑E

      
1
6

      
1
7

      
1
8

      
1
9

      
0
10

    

    

      nums[5]=0 → zeros=3 > 2 — SHRINK! 

      nums[0]=1 → not a zero, just move: windowStart=1

      nums[1]=1 → not a zero, just move: windowStart=2

      nums[2]=1 → not a zero, just move: windowStart=3

      nums[3]=0 → IS a zero! zeros=2, windowStart=4 — now zeros ≤ k, stop shrinking

      window=[4..5] • maxLength still = 5
    

  


  
  

    

      E=6,7,8,9
      All 1s — window expands, no shrinking needed
    

    

      
1
0

      
1
1

      
1
2

      
0
3

      
0
4 ↑S

      
0
5

      
1
6

      
1
7

      
1
8

      
1
9 ↑E

      
0
10

    

    
After E=9: zeros=1 ≤ 2 • window=[4..9] length=6 • maxLength = max(5,6) = 6 ↑

  


  
  

    

      E=10 — BEST CONFIRMED
    

    

      
1
0

      
1
1

      
1
2

      
0
3

      
0
4 ↑S

      
0
5

      
1
6

      
1
7

      
1
8

      
1
9

      
0
10 ↑E

    

    

      nums[10]=0 → zeros=2 ≤ 2 • window=[4..10] length=7

      maxLength = max(6, 7) = 7? No — wait, window [4..10] has 2 zeros (idx 5 and 10) and one at idx 4 = 3 zeros!

      zeros was 1 before E=10, now zeros=2 ≤ 2 • No shrink.

      window=[4..10] • maxLength = max(6, 7) = 7... but the expected answer is 6.

      ⚠️ Rechecking: at E=9 windowStart=4, zeros=1 (only idx 5). At E=10, zeros becomes 2. window=[4..10], size=7 contains 2 zeros (idx 5,10). Valid! maxLength=7? No, expected=6. Let’s retrace from E=5 shrink carefully...

      After E=5 shrink: windowStart=4, zeros=2 (idx 4 and 5 are zeros!). E=6..9 adds 1s, zeros stays 2. E=10 adds 0 → zeros=3 > k → SHRINK: nums[4]=0 → zeros=2, windowStart=5. window=[5..10] size=6. maxLength = max(6,6) = 6 ✅
    

  


  

    🎯 Final Answer: 6 ✅

    Each element was added once (windowEnd sweep) and removed at most once (windowStart shrink). Total operations = 2n at most → O(n).
  


  
  
Time & Space Complexity

  

    
ApproachTimeSpaceNote

    
      
Brute ForceO(n²)O(1)Nested loops; inner loop re-counts zeros

      
Sliding WindowO(n)O(1)Each element enters and leaves the window at most once

    
  


  

    Key Insight: The while-loop inside the for-loop looks like O(n²) but it’s actually O(n) total. windowStart only ever moves forward — it can advance at most n times across the entire run, so the inner while executes at most n times in total, not n times per iteration.
  


  
  
Code — All Approaches × All Languages


  
  

    

      Approach 1
      🐌 Brute Force — All Subarrays
      
        O(n²)
        O(1) space
      
    

    

      
      
      
      
    

    

    

    

    

  


  
  

    

      Approach 2
      ⚡ Variable Sliding Window — Expand Right, Shrink When Invalid
      
        O(n)
        O(1) space
      
    

    

      💡 Count zeros in window. While zeros > k: shrink from left (subtract zero if leaving element is 0).

      Record window length windowEnd - windowStart + 1 after every shrink phase.
    

    

      
      
      
      
    

    

    

    

    

  


  

  

    🎯 Interview Tip: This is the canonical variable-size sliding window template. Anytime you see "longest subarray with at most X of something" — count the thing, expand freely, shrink while count > limit. Direct variations: Longest Substring with At Most K Distinct Characters, Fruit Into Baskets, Longest Repeating Character Replacement. Once you have this pattern locked, those all fall immediately.