Frequently Asked — This problem has been reported multiple times in recent Amazon interviews. Prioritize this during revision.

Max Consecutive Ones III

Problem Statement

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

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: Flip the two 0s at indices 5 and 10 (or 3 and 4). 
One optimal window: [1,1,1,0,0,1,1,1,1,1] → indices 2-10 wait...
Actually: flip indices 5,10 → longest run of 1s = [0,0,1,1,1,1,1,1] from index 5 to 10 = length 6.
Better: indices 5-10 → [1,1,1,1,1,1] with 2 flips (index 5 and 10). Length 6.

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: Flip 3 zeros in the subarray from index 2 to 11.

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is 0 or 1
• 0 <= k <= nums.length

Difficulty: Medium (LC 1004)

---

Pattern Recognition

• What is the input structure? A binary array with a budget constraint (k flips).
• What are we optimizing? The length of the longest subarray containing at most k zeros.
• What pattern does this fit? Sliding Window. You maintain a window that contains at most k zeros. When the count of zeros exceeds k, shrink the window from the left.
• Why does this pattern fit? You are looking for the longest contiguous subarray satisfying a constraint (at most k zeros). The constraint is monotonic — adding elements can only increase the zero count, and removing from the left can only decrease it. This is the classic sliding window setup.

---

Approach

Brute Force — Check All Subarrays

For every pair (i, j), count zeros in nums[i..j]. If zeros <= k, update the max length.

best = 0
for i in 0..n-1:
    zeros = 0
    for j in i..n-1:
        if nums[j] == 0: zeros += 1
        if zeros <= k: best = max(best, j - i + 1)
        else: break

Time: O(n^2) — two nested loops. Space: O(1). Why insufficient: For n = 10^5, this is 10^10 operations — way too slow.

Optimal — Sliding Window

Key Insight: Reframe the problem: find the longest subarray with at most k zeros. Use two pointers (left, right) to maintain a window. Expand right to include elements. When zero count exceeds k, advance left until the count drops back to k.

Step-by-step:

1. Initialize left = 0, zeros = 0, max_len = 0.
2. For each right from 0 to n-1:
   • If nums[right] == 0, increment zeros.
   • While zeros > k, shrink from the left:
     • If nums[left] == 0, decrement zeros.
     • Increment left.
   • Update max_len = max(max_len, right - left + 1).
3. Return max_len.

function maxConsecutiveOnes(nums, k):
    left = 0, zeros = 0, max_len = 0
    for right in 0..n-1:
        if nums[right] == 0: zeros++
        while zeros > k:
            if nums[left] == 0: zeros--
            left++
        max_len = max(max_len, right - left + 1)
    return max_len

Time: O(n) — each element is visited by left and right at most once. Space: O(1).

---

Walkthrough

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

Step	right	nums[right]	zeros	left adjusted?	Window [left..right]	Length	max_len
1	0	1	0	No	[0..0]	1	1
2	1	0	1	No	[0..1]	2	2
3	2	1	1	No	[0..2]	3	3
4	3	1	1	No	[0..3]	4	4
5	4	0	2	No	[0..4]	5	5
6	5	0	3	Yes: nums[0]=1, left=1; nums[1]=0, zeros=2, left=2	[2..5]	4	5
7	6	1	2	No	[2..6]	5	5
8	7	1	2	No	[2..7]	6	6

Answer: 6 — the window [2..7] contains 2 zeros (indices 4 and 5), which we flip.

---

Implementation

TypeScript

function longestOnes(nums: number[], k: number): number {
    let left = 0;
    let zeros = 0;
    let maxLen = 0;

    for (let right = 0; right < nums.length; right++) {
        // Expand window — count zeros
        if (nums[right] === 0) zeros++;

        // Shrink window from left until we have at most k zeros
        while (zeros > k) {
            if (nums[left] === 0) zeros--;
            left++;
        }

        // Current window is valid — update best
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
}

C++

int longestOnes(vector<int>& nums, int k) {
    int left = 0, zeros = 0, maxLen = 0;

    for (int right = 0; right < (int)nums.size(); right++) {
        // Expand window — count zeros
        if (nums[right] == 0) zeros++;

        // Shrink window from left until we have at most k zeros
        while (zeros > k) {
            if (nums[left] == 0) zeros--;
            left++;
        }

        // Current window is valid — update best
        maxLen = max(maxLen, right - left + 1);
    }

    return maxLen;
}

Optimized variant — never shrink the window (only grow or slide):

TypeScript

/**
 * Instead of shrinking, just slide the window.
 * The window size never decreases — it either grows or stays the same.
 * This works because we only care about the MAXIMUM window size.
 */
function longestOnesOptimized(nums: number[], k: number): number {
    let left = 0;
    let zeros = 0;

    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) zeros++;

        if (zeros > k) {
            // Slide the window (don't shrink, just move left by 1)
            if (nums[left] === 0) zeros--;
            left++;
        }
    }

    // The window size at the end is the answer
    return nums.length - left;
}

C++

/*
 * Instead of shrinking, just slide the window.
 * The window size never decreases — it either grows or stays the same.
 * This works because we only care about the MAXIMUM window size.
 */
int longestOnesOptimized(vector<int>& nums, int k) {
    int left = 0, zeros = 0;

    for (int right = 0; right < (int)nums.size(); right++) {
        if (nums[right] == 0) zeros++;

        if (zeros > k) {
            // Slide the window (don't shrink, just move left by 1)
            if (nums[left] == 0) zeros--;
            left++;
        }
    }

    // The window size at the end is the answer
    return (int)nums.size() - left;
}

Watch out:

1. Using if instead of while for shrinking. If you use the standard shrinking approach, you must use while zeros > k because the window might need to shrink by more than one position. The if-based variant works only in the "never shrink" optimization where the window slides by exactly 1.
2. Off-by-one in window length. The window length is right - left + 1, not right - left. A single-element window where left == right has length 1.
3. Forgetting k = 0 case. When k = 0, you can flip no zeros. The answer is the longest run of existing 1s. The sliding window handles this correctly — the window shrinks immediately when it encounters a zero.

---

Complexity Analysis

	Time	Space
Brute Force	O(n^2)	O(1)
Sliding Window	O(n)	O(1)
Never-shrink variant	O(n)	O(1)

Bottleneck: Each pointer (left and right) moves at most n times, so the total work is O(2n) = O(n). No additional data structures are needed — just two pointers and a counter.

---

Edge Cases

1. All 1s — The entire array is the answer. zeros never exceeds k.
2. All 0s with k >= n — Flip everything. Answer is n.
3. All 0s with k = 0 — No flips allowed, no 1s exist. Answer is 0.
4. k >= number of zeros — You can flip all zeros. Answer is n.
5. Single element — Either [0] (answer is k >= 1 ? 1 : 0) or [1] (answer is 1).
6. k = n — You can flip the entire array. Answer is n regardless of content.

---

Related Problems

• LC 485 — Max Consecutive Ones — Simplest version: no flips allowed (k = 0). Just find the longest run of 1s.
• LC 487 — Max Consecutive Ones II — Allow flipping at most 1 zero (k = 1). Special case of this problem.
• LC 424 — Longest Repeating Character Replacement — Same sliding window pattern: longest substring where you can replace at most k characters.
• LC 340 — Longest Substring with At Most K Distinct Characters — Sliding window with a budget constraint on distinct characters.

---

What is Expected at Each Level

Junior: Recognize the sliding window pattern with guidance. Implement the basic version with while shrinking. May struggle with the boundary conditions.

Mid-level: Immediately identify this as a sliding window problem. Reframe "flip k zeros" as "longest subarray with at most k zeros." Write clean code. Discuss both shrinking and never-shrink variants. Handle edge cases.

Senior: Solve quickly with the optimized never-shrink variant. Explain why the window only needs to grow or slide. Extend to follow-up: "What if the array is a stream and you can't store it?" (Use a queue/deque of zero positions). Discuss the connection to other sliding window problems and when each variant applies.