42. Max Consecutive Ones III

🔗 LeetCode Problem: 1004. Max Consecutive Ones III
📊 Difficulty: Medium
🏷️ Topics: Array, Binary Search, Sliding Window, Prefix Sum

Problem Statement

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

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

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: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

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

---

🎨 Visual Understanding

The Problem Visualized

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

We can flip at most 2 zeros to ones.

Original: [1,1,1,0,0,0,1,1,1,1,0]
                 ↑ ↑             
         Flip these two zeros

Result:   [1,1,1,1,1,0,1,1,1,1,0]
               └─────┘
         Longest consecutive 1's = 6

Answer: 6

Key Observation: This is Similar to Problem #38!

Problem #38: Longest Repeating Character Replacement
- Replace at most k characters to make all same
- Valid if: windowLen - maxFreq <= k

This Problem: Max Consecutive Ones III
- Flip at most k zeros to ones
- Valid if: number of zeros in window <= k

The pattern is nearly identical!

Comparison:
┌────────────────────────────────────┬──────────────────────┐
│ Problem #38                        │ Problem #42          │
├────────────────────────────────────┼──────────────────────┤
│ Replace k chars                    │ Flip k zeros         │
│ windowLen - maxFreq <= k           │ zeroCount <= k       │
│ Track maxFreq (most common char)   │ Track zeroCount      │
│ Shrink when too many replacements  │ Shrink when too many │
│                                    │ zeros                │
└────────────────────────────────────┴──────────────────────┘

Visual Process

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

[1] → zeros = 0 ≤ 2 ✓, len = 1
[1,1] → zeros = 0 ≤ 2 ✓, len = 2
[1,1,1] → zeros = 0 ≤ 2 ✓, len = 3
[1,1,1,0] → zeros = 1 ≤ 2 ✓, len = 4
[1,1,1,0,0] → zeros = 2 ≤ 2 ✓, len = 5
[1,1,1,0,0,0] → zeros = 3 > 2 ✗
Shrink: [1,1,0,0,0] → zeros = 3 > 2 ✗
Shrink: [1,0,0,0] → zeros = 3 > 2 ✗
Shrink: [0,0,0] → zeros = 3 > 2 ✗
Shrink: [0,0] → zeros = 2 ≤ 2 ✓
[0,0,1] → zeros = 2 ≤ 2 ✓, len = 3
[0,0,1,1] → zeros = 2 ≤ 2 ✓, len = 4
[0,0,1,1,1] → zeros = 2 ≤ 2 ✓, len = 5
[0,0,1,1,1,1] → zeros = 2 ≤ 2 ✓, len = 6 ✓
[0,0,1,1,1,1,0] → zeros = 3 > 2 ✗
Shrink: [0,1,1,1,1,0] → zeros = 2 ≤ 2 ✓

Maximum: 6

---

🎯 Approach 1: Brute Force

The Most Natural Thinking 💭

Core Logic:

Try every subarray:
1. For each starting position i
2. Count zeros while expanding right
3. Stop when zeros exceed k
4. Track maximum length

Why This Works: - Checks all possibilities - Guaranteed to find answer - Easy to understand

Why This Fails Requirements: - Time complexity O(n²) - Recounts for overlapping windows - Too slow for large arrays - Not optimal for interviews

Implementation

public int longestOnes(int[] nums, int k) {
    int n = nums.length;
    int maxOnes = 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) {
                maxOnes = Math.max(maxOnes, j - i + 1);
            } else {
                break;  // Too many zeros
            }
        }
    }

    return maxOnes;
}

⏰ Time: O(n²) - for each start, expand until k+1 zeros
💾 Space: O(1) - only variables

---

✅ Approach 2: Sliding Window (Optimal)

The Breakthrough Insight 💡

Core Logic:

Use variable-size sliding window:

Valid window condition:
Number of zeros in window <= k

Algorithm:
1. Expand window: Add right element
2. Count zeros in window
3. If zeros > k: Shrink from left
4. Track maximum length

Key insight: Only need to count zeros, not all elements

Visual Explanation:

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

Window: [1,1,1,0,0]
zeros = 2 ≤ 2 ✓, length = 5

Window: [1,1,1,0,0,0]
zeros = 3 > 2 ✗
Need to shrink!

After shrinking: [0,0]
zeros = 2 ≤ 2 ✓

Continue expanding: [0,0,1,1,1,1]
zeros = 2 ≤ 2 ✓, length = 6 ✓

Why This Works:

Sliding window maintains invariant:
"At most k zeros in window"

When zeros > k:
- Shrink from left until zeros ≤ k
- Each element visited at most twice
- Total time: O(n)

Tracking:
- zeroCount: number of zeros in current window
- When removing element: if it's 0, decrease zeroCount
- When adding element: if it's 0, increase zeroCount

Implementation (Simple Counter)

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

    for (int right = 0; right < nums.length; right++) {
        // Expand window: add right element
        if (nums[right] == 0) {
            zeros++;
        }

        // Shrink window while too many zeros
        while (zeros > k) {
            if (nums[left] == 0) {
                zeros--;
            }
            left++;
        }

        // Update maximum length
        maxOnes = Math.max(maxOnes, right - left + 1);
    }

    return maxOnes;
}

⏰ Time: O(n) - each element visited at most twice
💾 Space: O(1) - only variables

---

🔍 Step-by-Step Execution

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

Initial State:
═══════════════════════════════════════════════════════════════════
nums = [1,1,1,0,0,0,1,1,1,1,0]
k = 2
left = 0, zeros = 0, maxOnes = 0


Step 1: right = 0, num = 1
═══════════════════════════════════════════════════════════════════
nums[0] = 1 (not zero)
zeros = 0

zeros ≤ 2 ✓ Valid

Window: [1]
maxOnes = max(0, 0-0+1) = 1

left = 0, zeros = 0, maxOnes = 1


Step 2: right = 1, num = 1
═══════════════════════════════════════════════════════════════════
nums[1] = 1 (not zero)
zeros = 0

zeros ≤ 2 ✓ Valid

Window: [1,1]
maxOnes = max(1, 1-0+1) = 2

left = 0, zeros = 0, maxOnes = 2


Step 3: right = 2, num = 1
═══════════════════════════════════════════════════════════════════
nums[2] = 1 (not zero)
zeros = 0

zeros ≤ 2 ✓ Valid

Window: [1,1,1]
maxOnes = max(2, 2-0+1) = 3

left = 0, zeros = 0, maxOnes = 3


Step 4: right = 3, num = 0
═══════════════════════════════════════════════════════════════════
nums[3] = 0 (zero!)
zeros = 1

zeros ≤ 2 ✓ Valid

Window: [1,1,1,0]
maxOnes = max(3, 3-0+1) = 4

left = 0, zeros = 1, maxOnes = 4


Step 5: right = 4, num = 0
═══════════════════════════════════════════════════════════════════
nums[4] = 0 (zero!)
zeros = 2

zeros ≤ 2 ✓ Valid

Window: [1,1,1,0,0]
maxOnes = max(4, 4-0+1) = 5

left = 0, zeros = 2, maxOnes = 5


Step 6: right = 5, num = 0
═══════════════════════════════════════════════════════════════════
nums[5] = 0 (zero!)
zeros = 3

zeros > 2 ✗ Invalid!

Need to shrink:

Shrink iteration 1:
  nums[0] = 1 (not zero)
  left = 1
  zeros = 3 > 2 ✗, continue

Shrink iteration 2:
  nums[1] = 1 (not zero)
  left = 2
  zeros = 3 > 2 ✗, continue

Shrink iteration 3:
  nums[2] = 1 (not zero)
  left = 3
  zeros = 3 > 2 ✗, continue

Shrink iteration 4:
  nums[3] = 0 (zero!)
  zeros = 2
  left = 4
  zeros = 2 ≤ 2 ✓, stop shrinking

Window: [0,0]
maxOnes = max(5, 5-4+1) = 5 (no change)

left = 4, zeros = 2, maxOnes = 5


Step 7: right = 6, num = 1
═══════════════════════════════════════════════════════════════════
nums[6] = 1 (not zero)
zeros = 2

zeros ≤ 2 ✓ Valid

Window: [0,0,1]
maxOnes = max(5, 6-4+1) = 5 (no change)

left = 4, zeros = 2, maxOnes = 5


Step 8: right = 7, num = 1
═══════════════════════════════════════════════════════════════════
nums[7] = 1 (not zero)
zeros = 2

zeros ≤ 2 ✓ Valid

Window: [0,0,1,1]
maxOnes = max(5, 7-4+1) = 5 (no change)

left = 4, zeros = 2, maxOnes = 5


Step 9: right = 8, num = 1
═══════════════════════════════════════════════════════════════════
nums[8] = 1 (not zero)
zeros = 2

zeros ≤ 2 ✓ Valid

Window: [0,0,1,1,1]
maxOnes = max(5, 8-4+1) = 5

left = 4, zeros = 2, maxOnes = 5


Step 10: right = 9, num = 1
═══════════════════════════════════════════════════════════════════
nums[9] = 1 (not zero)
zeros = 2

zeros ≤ 2 ✓ Valid

Window: [0,0,1,1,1,1]
maxOnes = max(5, 9-4+1) = 6 ✓

left = 4, zeros = 2, maxOnes = 6


Step 11: right = 10, num = 0
═══════════════════════════════════════════════════════════════════
nums[10] = 0 (zero!)
zeros = 3

zeros > 2 ✗ Invalid!

Need to shrink:

Shrink iteration 1:
  nums[4] = 0 (zero!)
  zeros = 2
  left = 5
  zeros = 2 ≤ 2 ✓, stop shrinking

Window: [0,1,1,1,1,0]
maxOnes = max(6, 10-5+1) = 6 (no change)

left = 5, zeros = 2, maxOnes = 6


═══════════════════════════════════════════════════════════════════
🎯 FINAL RESULT: 6
═══════════════════════════════════════════════════════════════════

---

🔍 Edge Cases

Case 1: k = 0 (no flips allowed)
Input: nums = [1,1,0,1,1], k = 0
Output: 2
Explanation: Longest run of 1's without flipping

Case 2: k >= number of zeros
Input: nums = [0,0,1,1,0], k = 5
Output: 5
Explanation: Can flip all zeros

Case 3: All zeros
Input: nums = [0,0,0,0], k = 2
Output: 2
Explanation: Can only flip 2

Case 4: All ones
Input: nums = [1,1,1,1], k = 2
Output: 4
Explanation: No zeros to flip

Case 5: k = 0 with all ones
Input: nums = [1,1,1], k = 0
Output: 3

Case 6: Single element
Input: nums = [1], k = 0
Output: 1

Case 7: Single zero with k=1
Input: nums = [0], k = 1
Output: 1
Explanation: Flip the only zero

Case 8: Complex pattern
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: Flip two zeros in the middle

---

Common Mistakes

Mistake 1: Not tracking zero count
❌ Wrong: 
    // Trying to track 1's count instead of 0's
✓ Right: 
    int zeros = 0;
    if (nums[right] == 0) zeros++;
Reason: Need to count zeros to know if we can flip

Mistake 2: Using if instead of while for shrinking
❌ Wrong: 
    if (zeros > k) {
        // Shrink once
    }
✓ Right: 
    while (zeros > k) {
        // Keep shrinking until valid
    }
Reason: May need to remove multiple elements

Mistake 3: Forgetting to decrease zero count when shrinking
❌ Wrong: 
    while (zeros > k) {
        left++;
        // Forgot to check if nums[left] was 0
    }
✓ Right: 
    while (zeros > k) {
        if (nums[left] == 0) {
            zeros--;
        }
        left++;
    }
Reason: Must maintain accurate zero count

Mistake 4: Updating maxOnes inside while loop
❌ Wrong: 
    while (zeros > k) {
        maxOnes = Math.max(maxOnes, right - left + 1);
        // shrink...
    }
✓ Right: 
    while (zeros > k) {
        // shrink...
    }
    maxOnes = Math.max(maxOnes, right - left + 1);
Reason: Update only when window is valid

Mistake 5: Checking nums[right] before incrementing zeros
❌ Wrong: 
    if (nums[right] == 1) {  // Wrong check
        zeros++;
    }
✓ Right: 
    if (nums[right] == 0) {  // Check for zero
        zeros++;
    }
Reason: Count zeros, not ones!

Mistake 6: Not handling k = 0
❌ Wrong: 
    // Assuming k > 0
✓ Right: 
    // Algorithm works for k = 0 naturally
Reason: When k=0, finds longest run without zeros

---

🎯 Key Takeaways

⚡ Algorithm Comparison

Approach 1: Brute Force
  Time: O(n²)
  Space: O(1)
  Use: Only for understanding

Approach 2: Sliding Window (RECOMMENDED)
  Time: O(n)
  Space: O(1)
  Use: Optimal solution, best for interviews

🔑 The Core Insight

Valid Window Condition:
Number of zeros in window <= k

Comparison with Problem #38:
═══════════════════════════════════════════════════════════════

Problem #38: Longest Repeating Character Replacement
- Valid if: windowLen - maxFreq <= k
- Track: maxFreq (most common character)
- Shrink when: replacements needed > k

Problem #42: Max Consecutive Ones III
- Valid if: zeros <= k
- Track: zeros (count of zeros in window)
- Shrink when: zeros > k

Both use same pattern:
1. Variable-size sliding window
2. Expand always
3. Shrink when constraint violated
4. Track maximum length

Simplified Formula:
═══════════════════════════════════════════════════════════════

For binary array (only 0's and 1's):
- We want all 1's
- Can flip k zeros
- Valid window has ≤ k zeros

Algorithm:
1. Count zeros in window
2. If zeros > k: shrink from left
3. Track max window size

Template:
═══════════════════════════════════════════════════════════════

int left = 0, zeros = 0, maxLen = 0;

for (int right = 0; right < n; right++) {
    // Expand: count zeros
    if (nums[right] == 0) zeros++;

    // Shrink: while too many zeros
    while (zeros > k) {
        if (nums[left] == 0) zeros--;
        left++;
    }

    // Update max
    maxLen = Math.max(maxLen, right - left + 1);
}

return maxLen;

🎯 Pattern Recognition

Problem Type: Longest Subarray with Flipping Constraint
Core Pattern: Variable-Size Sliding Window

When to Apply:
✓ Finding longest subarray
✓ Can modify elements (flip, replace)
✓ Limited number of modifications (k)
✓ Binary array or similar constraint
✓ Want O(n) time complexity

Recognition Keywords:
- "Flip at most k" → Track count of flipped elements
- "Maximum consecutive" → Longest subarray
- "Binary array" → Only two values (0 and 1)
- "At most k zeros/ones" → Sliding window with counter

Relationship to Other Problems:
- Problem #38 (Character Replacement): Same pattern, different constraint
- Problem #36 (Minimum Size Subarray): Variable window, different goal
- Problem #37 (At Most K Distinct): Same pattern, track distinct count

Related Problems:
- Longest Repeating Character Replacement (LC 424)
- Minimum Window Substring (LC 76)
- Longest Substring with At Most K Distinct Characters (LC 340)

🧠 Interview Strategy

Step 1: "Need longest subarray of 1's with at most k flips"
Step 2: "This is a sliding window problem"
Step 3: "Track number of zeros in window"
Step 4: "Valid window has zeros <= k"
Step 5: "Expand always, shrink when zeros > k"
Step 6: "O(n) time, O(1) space"

Key Points to Mention:
- Variable-size sliding window
- Count zeros in current window
- Valid condition: zeros <= k
- Shrink while zeros > k
- Remember to decrease zero count when shrinking
- Update maxOnes after shrinking
- O(n) time, each element visited twice max
- O(1) space, only counter variable

Similar to Problem #38:
"This is similar to Longest Repeating Character Replacement,
but simpler - we only need to count zeros instead of tracking
character frequencies."

This shows good pattern recognition! 🏆

---

📝 Quick Revision Notes

🎯 Core Concept:

Variable-size sliding window tracking zero count. Valid window: zeros ≤ k. Expand always, shrink while zeros > k.

⚡ Quick Implementation:

import java.util.HashMap;

class Test {
  // Similar to prob 38
  public int longestOnes(int[] a, int k) {
    int res = Integer.MIN_VALUE;
    int len = a.length;
    int left = 0;
    int right = 0;
    int numOfZeros = 0;

    while (right < len) {
      if (a[right] == 0) {
        numOfZeros++;
      }

      // Number of zeros in the window exceeded k.
      while (left <= right && numOfZeros > k) {
        if (a[left] == 0) {
          numOfZeros--;
        }

        left++;
      }

      res = Math.max(res, right - left + 1);

      right++;
    }

    return res == Integer.MIN_VALUE ? 0 : res;
  }

  public static void main(String[] args) {
    Test t = new Test();
    System.out.println(t.longestOnes(new int[] { 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0 }, 2));
    System.out.println(t.longestOnes(new int[] { 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1 }, 3));
    System.out.println(t.longestOnes(new int[] { 0, 0, 0, 0 }, 0));
  }
}

🔑 Key Insights:

• Valid condition: zeros <= k
• Track: Number of zeros in window (not ones!)
• Expand: Always add right element
• Count zeros: if (nums[right] == 0) zeros++
• Shrink: While zeros > k
• Decrease count: if (nums[left] == 0) zeros--
• Update maxOnes: After shrinking (when valid)
• Time: O(n) - each element visited at most twice
• Space: O(1) - only counter variable
• Similar to: Problem #38 but simpler (just count zeros)

🎪 Memory Aid:

"Count ZEROS, flip at most K! Shrink when OVER k!"
Think: "Too many zeros? Shrink! Track max window!"

💡 Connection to Problem #38:

Problem #38: windowLen - maxFreq <= k (complex)
Problem #42: zeros <= k (simpler!)

Same pattern, simpler constraint!

---

Related Patterns

• Longest Repeating Character Replacement (LC 424)
• Longest Substring with At Most K Distinct Characters (LC 340)
• Minimum Window Substring (LC 76)
• Minimum Size Subarray Sum (LC 209)

---

Happy practicing! 🎯