Pseudo-Code

text
function bruteForce(nums, k):
    max_len = 0
    n = length of nums
    for i from 0 to n-1:
        for j from i to n-1:
            zero_count = 0
            for p from i to j:
                if nums[p] == 0:
                    zero_count += 1
            if zero_count <= k:
                max_len = max(max_len, j - i + 1)
    return max_len

Complexity Analysis

The time complexity of this approach is O(N³) because of the three nested loops (or O(N²) if the zero count is maintained incrementally in the inner loop). Given the constraint nums.length <= 10^5, an O(N²) solution performs approximately 10^{10} operations, which far exceeds the typical limit of 10^8 operations per second allowed by online judges. This will result in a Time Limit Exceeded (TLE) error.

Core Insight for Max Consecutive Ones III

The key intuition for LeetCode 1004 is to reframe the problem statement. Instead of thinking about "flipping" zeros, we should view the problem as finding the longest subarray with at most k zeros. If a subarray has k or fewer zeros, we can theoretically flip all of them to 1s to form a consecutive sequence of 1s.

The sliding window technique allows us to maintain a valid window [left, right] where the count of zeros is always less than or equal to k.

1. Expansion: We extend the window to the right (right pointer) to try and find a longer valid subarray.
2. Contraction: If adding a new element causes the zero count to exceed k, the window becomes invalid. To restore validity, we shrink the window from the left (left pointer) until the zero count drops back to k.
3. Invariant: Throughout the execution, the window defined by [left, right] contains at most k zeros.

Visual Description: Imagine a window expanding over the array. The right edge moves forward, consuming elements. When a zero is consumed, an internal counter increments. If this counter exceeds k, the left edge of the window moves forward, dropping elements. If a zero is dropped, the counter decrements. This "caterpillar-like" movement ensures we efficiently check all valid windows without redundant recalculations.

Execution Flow

Let's trace the algorithm with nums = [1,1,1,0,0,0,1,1,1,1,0] and k = 2.

1. Initialization: left = 0, right = 0, zeros = 0, max_len = 0.
2. Steps 0-2 (Indices 0, 1, 2): nums[right] is 1. zeros remains 0. max_len updates to 3.
3. Step 3 (Index 3): nums[3] is 0. zeros becomes 1. 1 <= 2, valid. max_len updates to 4.
4. Step 4 (Index 4): nums[4] is 0. zeros becomes 2. 2 <= 2, valid. max_len updates to 5.
5. Step 5 (Index 5): nums[5] is 0. zeros becomes 3. Constraint violated (3 > 2).
   • Shrink: nums[left] (index 0) is 1. left moves to 1. zeros is still 3.
   • Shrink: nums[left] (index 1) is 1. left moves to 2. zeros is still 3.
   • Shrink: nums[left] (index 2) is 1. left moves to 3. zeros is still 3.
   • Shrink: nums[left] (index 3) is 0. zeros becomes 2. left moves to 4.
   • Window is now [4, 5] (values 0, 0). Valid. max_len remains 5.
6. Steps 6-9: right moves through 1s. Window expands. zeros remains 2. max_len updates eventually to 6 (window [5, 10]).

The algorithm correctly identifies the longest valid window length as 6.

Proof of Correctness

The correctness relies on the invariant that for any right index, the algorithm finds the smallest left index such that the subarray nums[left...right] contains at most k zeros.

1. Safety: The while loop ensures that we never consider an invalid window for the maximum length calculation. If zeros > k, we shrink until valid.
2. Optimality: Since right iterates from 0 to n-1 and left only moves forward when necessary, we consider the largest possible valid window ending at every index right. The global maximum of these local maximums must be the overall maximum length.

Reference Implementation

C++ Solution for LeetCode 1004

cpp
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0;
        int right = 0;
        int zeros = 0;
        int max_len = 0;
        
        while (right < nums.size()) {
            // Expand the window
            if (nums[right] == 0) {
                zeros++;
            }
            
            // Shrink the window if constraint is violated
            while (zeros > k) {
                if (nums[left] == 0) {
                    zeros--;
                }
                left++;
            }
            
            // Update maximum length found so far
            max_len = max(max_len, right - left + 1);
            right++;
        }
        
        return max_len;
    }
};

Java Solution for LeetCode 1004

java
class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0;
        int right = 0;
        int zeros = 0;
        int maxLen = 0;
        
        while (right < nums.length) {
            // Add new element to the window
            if (nums[right] == 0) {
                zeros++;
            }
            
            // Contract window if invalid
            while (zeros > k) {
                if (nums[left] == 0) {
                    zeros--;
                }
                left++;
            }
            
            // Update global maximum
            maxLen = Math.max(maxLen, right - left + 1);
            right++;
        }
        
        return maxLen;
    }
}

Python Solution for LeetCode 1004

python
class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0
        zeros = 0
        max_len = 0
        
        for right in range(len(nums)):
            # Expand window logic
            if nums[right] == 0:
                zeros += 1
            
            # Shrink window logic
            while zeros > k:
                if nums[left] == 0:
                    zeros -= 1
                left += 1
            
            # Update max length
            max_len = max(max_len, right - left + 1)
            
        return max_len

Q: Can I use recursion for this problem? Mistake: Attempting a recursive DFS to simulate flipping bits. Why: This treats the problem as a decision tree (flip or don't flip), which is O(2^N). Consequence: Immediate TLE and stack overflow for large inputs.