L4. Max Consecutive Ones III | Two Pointers and Sliding Window

This chapter covers the classic Max Consecutive Ones III problem, exploring its progression from a naive brute-force approach to an optimal $O(N)$ sliding window solution without an inner shrinking loop.

1. Problem Statement and Objective

We are given a binary array (nums) containing only 0s and 1s, and an integer K. Our objective is to find the maximum number of consecutive 1s we can get in the array if we are allowed to flip at most K zeros.

Real-Life Analogy: The Window of Tolerance

Analogy: Imagine looking at a long train of boxcars where some cars are empty (0) and some are full (1). You have a special budget of tarps (K flips) to cover up empty cars so the entire section looks packed. Your goal is to slide a viewing window across the train to find the longest contiguous block of cars you can make look entirely full using at most K tarps.

2. Converting the Problem Statement

When faced with phrasing like "maximum consecutive ones with at most K zeros flipped," we can reframe the problem into a standard subarray pattern:

Conceptually: The problem is identical to finding the longest subarray that contains at most K zeros.

If a contiguous window has zero count $\le K$, it is a valid candidate. Our goal is to maximize the length of this window (j - i + 1).

3. Naive Brute Force Approach ($O(N^2)$)

The most intuitive approach is to generate all possible subarrays, count the number of zeros in each, and track the maximum length where zero count $\le K$.

Brute Force Code Implementation

class Solution {
    public int longestOnes(int[] nums, int k) {
        int maxLength = 0;
        int n = nums.length;
        
        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) {
                    maxLength = Math.max(maxLength, j - i + 1);
                } else {
                    break; // Stop expanding if zeros exceed K
                }
            }
        }
        return maxLength;
    }
}

• Time Complexity: $O(N^2)$ in the worst case, as we iterate through possible starting and ending points.
• Space Complexity: $O(1)$ auxiliary space.

4. Better Approach: Standard Sliding Window with Inner While Loop ($O(2N)$)

To achieve linear time complexity, we use a Two-Pointer / Sliding Window approach. We maintain a window bounded by a left pointer (L) and a right pointer (R), along with a running count of zeros.

Execution Flow Walkthrough

1. Expand R to the right, incorporating elements into the window.
2. If nums[R] == 0, increment our zeros count.
3. If zeros > K, the window is invalid. We must shrink the window from the left (L++) until zeros drops back to $\le K$.
4. At each valid step, calculate window length R - L + 1 and update maxLength.

Standard Sliding Window Code

class Solution {
    public int longestOnes(int[] nums, int k) {
        int maxLen = 0, l = 0, r = 0, zeros = 0;
        int n = nums.length;
        
        while (r < n) {
            if (nums[r] == 0) {
                zeros++;
            }
            
            // Shrink window if zeros exceed K
            while (zeros > k) {
                if (nums[l] == 0) {
                    zeros--;
                }
                l++;
            }
            
            if (zeros <= k) {
                maxLen = Math.max(maxLen, r - l + 1);
            }
            r++;
        }
        return maxLen;
    }
}

• Time Complexity: $O(2N)$ because in the worst case, both R and L traverse the array.
• Space Complexity: $O(1)$.

5. Optimal Approach: Eliminating the Inner While Loop ($O(N)$)

An insightful optimization for elite interviews is eliminating the inner while loop entirely.

The Core Insight

Notice that we are searching for the maximum length. Once our window reaches a maximum size, we never actually need the window size to shrink. Even if zeros > K, we can simply slide the window forward with a fixed maximum size, only letting L move forward by at most one position when a zero is encountered.

Key Rule: We do not allow the window to shrink below its historical maximum size. L only advances step-by-step alongside R when violations occur, preserving the max length found so far until a larger valid window can be formed.

6. Complete Optimal Code Implementation

Here is the fully optimized Java implementation running in strict $O(N)$ time without an inner while loop:

class Solution {
    public int longestOnes(int[] nums, int k) {
        int maxLen = 0, l = 0, r = 0, zeros = 0;
        int n = nums.length;
        
        while (r < n) {
            if (nums[r] == 0) {
                zeros++;
            }
            
            // If zeros exceed K, shift left pointer by exactly 1
            if (zeros > k) {
                if (nums[l] == 0) {
                    zeros--;
                }
                l++;
            }
            
            if (zeros <= k) {
                maxLen = Math.max(maxLen, r - l + 1);
            }
            
            r++;
        }
        return maxLen;
    }
}

7. Complexity Comparison Table

8. Summary and Key Takeaways

• Problem Translation: Finding the maximum consecutive ones with at most K zeros flipped is equivalent to finding the longest subarray with at most K zeros.
• Two-Pointer Foundation: Sliding window techniques utilize a left (L) and right (R) pointer to dynamically evaluate contiguous segments.
• Window Expansion: The right pointer (R) greedily expands the window to test larger possible lengths.
• Constraint Management: When zero counts exceed K, window adjustments maintain validity.
• Optimization Principle: To achieve strict $O(N)$ time without an inner loop, prevent the window size from shrinking; instead, slide it forward at a fixed maximum size once a peak is established.
• Space Efficiency: All sliding window solutions achieve $O(1)$ auxiliary space complexity by operating directly on the input array.