Introduction

LeetCode 1004: Max Consecutive Ones III is a classic sliding window problem that challenges your understanding of arrays, window manipulation, and frequency counting.

The goal is to find the longest subarray of consecutive 1's in a binary array if you are allowed to flip at most K zeros to 1’s.

This problem is an excellent example of transforming a brute-force solution into a linear-time efficient approach using the sliding window pattern.

If you’d like to try solving the problem first, you can attempt it here:

Try the problem on LeetCode:

https://leetcode.com/problems/max-consecutive-ones-iii/

Problem Understanding

You are given:

1. A binary array nums containing only 0's and 1's
2. An integer k representing the maximum number of zeros you can flip

You need to return the length of the longest contiguous subarray of 1's after flipping at most k zeros.

Examples:

A naive approach would check every possible subarray, flip zeros, and count consecutive ones:

1. Time Complexity: O(n²) → too slow for large arrays
2. Inefficient for constraints up to 10⁵ elements

Key Idea: Sliding Window with Zero Count

Instead of brute-force, notice that:

1. We only care about how many zeros are in the current window
2. We can maintain a sliding window [i, j]
3. Keep a counter z for zeros in the window
4. Expand the window by moving j
5. If z exceeds k, shrink the window from the left by moving i and decrementing z for each zero removed

Intuition:

1. The window always contains at most k zeros
2. The length of the window gives the maximum consecutive ones achievable with flips

This allows linear traversal of the array with O(1) space, making it optimal.

Approach (Step-by-Step)

1. Initialize pointers: i = 0, j = 0
2. Initialize z = 0 (zeros count in current window) and co = 0 (max length)
3. Iterate j from 0 to nums.length - 1:
4. If nums[j] == 0, increment z
5. Check z:
6. If z <= k: window is valid → update co = max(co, j - i + 1)
7. Else: shrink window by moving i until z <= k, decrement z for zeros leaving window
8. Continue expanding window with j
9. Return co as the maximum consecutive ones

Optimization:

1. Only need one variable for zeros count
2. Avoids recomputing sums or scanning subarrays repeatedly

Implementation (Java)

Dry Run Example

Input:

Execution:

Output:

Complexity Analysis

1. Time Complexity: O(n) → Each element is visited at most twice (once when j moves, once when i moves)
2. Space Complexity: O(1) → Only counters and pointers used

Edge Cases Considered

1. k = 0 → cannot flip any zeros, just count consecutive ones
2. Array with all 1’s → return full length
3. Array with all 0’s → return min(k, length)
4. Single element arrays → works correctly

Sliding Window Pattern Importance

This problem is a perfect example of the sliding window pattern:

1. Use a window to track a condition (max zeros allowed)
2. Expand and shrink dynamically based on constraints
3. Efficiently computes maximum/minimum contiguous subarray lengths

It also demonstrates counting with limited violations – a key interview concept.

Conclusion

By tracking zeros with a sliding window, we convert a naive O(n²) problem into O(n) linear time.

Understanding this pattern allows you to solve:

1. Max consecutive ones/zeros problems
2. Longest substring/subarray with constraints
3. Subarray problems with limited replacements or violations

Once mastered, this approach applies to many binary array and string problems efficiently.