1004. Max Consecutive Ones III

Quick Identifier

• Topic: sliding-window
• Pattern: Variable Window with Limited Flips (Need/Have + budget)
• Hint: You can flip at most k zeros to 1. Use a sliding window that tracks the number of zeros in the current window; when it exceeds k, shrink from the left.
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Microsoft, Facebook
• LeetCode: 1004

Quick Sights

• Time Complexity: O(n) – each index is visited at most twice (once by the right pointer, once by the left pointer).
• Space Complexity: O(1) – only a few integer counters are needed.
• Core Mechanism: Maintain a window [left, right] and a count of zeros inside it. Expand right; if zeros > k, move left forward until zeros ≤ k. The window length is the candidate answer.

Concept Explanation

Think of the binary array as a road with potholes (0). You have a limited number of repair kits (k). The goal is to drive as far as possible without running out of kits.

1. Expansion – drive forward (right) and count encountered potholes.
2. Budget Check – if potholes exceed k, you must backtrack (left) and start repairing the leftmost potholes (effectively “un‑use” those repair kits) until the budget is satisfied again.
3. Recording – the longest stretch you successfully drove with ≤ k repairs is the answer.

Diagram

Study Pattern (SDE3+)

• 0‑3 min: Explain the “repair‑kit budget” analogy and why a variable‑size window is appropriate.
• Implementation pass: Emphasise the zeros counter and the while zeros > k loop that moves left.
• 5 min extension: Discuss how to adapt the approach if the input were a stream of bits (online algorithm) – you would still keep the same counters.

Approaches

• Brute force – examine all O(n²) subarrays and count zeros – too slow.
• Prefix‑sum + binary search – could work but adds O(n log n) complexity.
• Optimal – sliding window with zero‑budget – O(n) time, O(1) space. (Always pick this)

Optimal Solution

Go

func longestOnes(nums []int, k int) int {
    left, zeros, best := 0, 0, 0
    for right, val := range nums {
        if val == 0 {
            zeros++
        }
        for zeros > k {
            if nums[left] == 0 {
                zeros--
            }
            left++
        }
        if length := right - left + 1; length > best {
            best = length
        }
    }
    return best
}

JavaScript

function longestOnes(nums, k) {
    let left = 0, zeros = 0, best = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) zeros++;
        while (zeros > k) {
            if (nums[left] === 0) zeros--;
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Walkthrough

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

• Expand until index 5 → zeros = 3 > k, shrink left until zeros = 2 (left moves to index 2).
• Continue expanding; the longest valid window found is length 6 ([0,1,1,1,1,0] after appropriate shifts).

Edge Cases

• k >= total zeros → answer is len(nums).
• All ones → answer is len(nums).
• All zeros with k = 0 → answer is 0.

Pitfalls

• Forgetting to decrement zeros when moving left past a zero.
• Using >= k instead of > k in the while condition, which would incorrectly shrink the window.

Similar Problems

• [3. Longest Substring Without Repeating Characters] – variable window with distinct count.
• [209. Minimum Size Subarray Sum] – variable window with sum ≥ target.
• [239. Sliding Window Maximum] – different pattern (monotonic deque).

Mind‑Map Tags

#sliding-window #variable-window #budget #zero‑flip #medium