Max Consecutive Ones III

🎯

Max Consecutive Ones III

mediumSLIDING_WINDOWAmazonGoogleFacebook

Imagine you are streaming a binary signal and want to find the longest segment where you can flip at most K zeros to ones to maintain a strong signal.

💡 This problem is about finding the longest subarray with a constraint on how many zeros can be flipped to ones. Beginners often struggle because the window size is variable and the constraint requires careful tracking, which is a classic use case for the sliding window technique.

📋

Problem Statement

Given a binary array nums and an integer k, return the maximum number of consecutive 1's in the array if you can flip at most k 0's to 1's. Input: nums (list of 0s and 1s), k (integer). Output: integer representing the length of the longest subarray with at most k zeros.

1 ≤ nums.length ≤ 10^5nums[i] is either 0 or 10 ≤ k ≤ nums.length

💡

Example

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

Output6

Flip two zeros at positions 5 and 10 to get the longest consecutive ones subarray of length 6.

Input"nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3"

Output10

Flip three zeros to get the longest consecutive ones subarray of length 10.

• All elements are 1 → output is length of array
• All elements are 0 and k = 0 → output is 0
• k is equal to array length → output is length of array
• Array length is 1 → output is 1 if element is 1 or k > 0, else 0

⚠️

Common Mistakes

Not shrinking the window when zero count exceeds k

Leads to incorrect max length or infinite loop

✅ Add a while loop to move left pointer until zero count ≤ k

Counting zeros inside inner loop repeatedly in brute force

Causes time limit exceeded due to O(n^3) complexity

✅ Count zeros incrementally or use sliding window to avoid repeated counting

Incorrectly updating max length before shrinking window

May count invalid windows with too many zeros

✅ Update max length only after ensuring zero count ≤ k

Not handling edge cases like all ones or all zeros properly

Incorrect output or runtime errors

✅ Test and handle edge cases explicitly or ensure code logic covers them

Using data structures inefficiently (e.g., shifting array in JS)

Causes performance degradation

✅ Use deque or pointers to avoid costly operations

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by checking every possible subarray and counting zeros, which is intuitive but inefficient.

Intuition

Check every subarray and count how many zeros it contains. If zeros are within k, update the maximum length.

Algorithm

1. Initialize max_length to 0.
2. Use two nested loops to consider every subarray.
3. Count zeros in the current subarray.
4. If zeros ≤ k, update max_length with the subarray length.

💡 The nested loops and zero counting make this approach straightforward but inefficient, which helps grasp the problem's core.

</>

Code

def longestOnes(nums, k):
    max_length = 0
    n = len(nums)
    for start in range(n):
        zeros_count = 0
        for end in range(start, n):
            if nums[end] == 0:
                zeros_count += 1
            if zeros_count > k:
                break
            max_length = max(max_length, end - start + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    print(longestOnes([1,1,1,0,0,0,1,1,1,1,0], 2))  # Output: 6

Line Notes

max_length = 0Initialize to keep track of the longest valid subarray found so far

for start in range(n)Outer loop selects the start index of the subarray

zeros_count = 0Reset zero count for each new start index

if nums[end] == 0Count zeros in the current subarray

if zeros_count > kStop expanding if zero count exceeds allowed flips

max_length = max(max_length, end - start + 1)Update max length if current subarray is valid

public class Solution {
    public static int longestOnes(int[] nums, int k) {
        int maxLength = 0;
        int n = nums.length;
        for (int start = 0; start < n; start++) {
            int zerosCount = 0;
            for (int end = start; end < n; end++) {
                if (nums[end] == 0) zerosCount++;
                if (zerosCount > k) break;
                maxLength = Math.max(maxLength, end - start + 1);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,0,0,0,1,1,1,1,0};
        System.out.println(longestOnes(nums, 2)); // Output: 6
    }
}

Line Notes

int maxLength = 0;Initialize max length to track longest valid subarray

for (int start = 0; start < n; start++)Outer loop picks start index

int zerosCount = 0;Reset zero count for each new start

if (nums[end] == 0) zerosCount++;Count zeros in current subarray

if (zerosCount > k) break;Stop if zero count exceeds k

maxLength = Math.max(maxLength, end - start + 1);Update max length if valid

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestOnes(vector<int>& nums, int k) {
    int maxLength = 0;
    int n = nums.size();
    for (int start = 0; start < n; start++) {
        int zerosCount = 0;
        for (int end = start; end < n; end++) {
            if (nums[end] == 0) zerosCount++;
            if (zerosCount > k) break;
            maxLength = max(maxLength, end - start + 1);
        }
    }
    return maxLength;
}

int main() {
    vector<int> nums = {1,1,1,0,0,0,1,1,1,1,0};
    cout << longestOnes(nums, 2) << endl; // Output: 6
    return 0;
}

Line Notes

int maxLength = 0;Initialize max length to track longest valid subarray

for (int start = 0; start < n; start++)Outer loop selects start index

int zerosCount = 0;Reset zero count for each new start

if (nums[end] == 0) zerosCount++;Count zeros in current subarray

if (zerosCount > k) break;Stop expanding if zero count exceeds k

maxLength = max(maxLength, end - start + 1);Update max length if current subarray is valid

function longestOnes(nums, k) {
    let maxLength = 0;
    const n = nums.length;
    for (let start = 0; start < n; start++) {
        let zerosCount = 0;
        for (let end = start; end < n; end++) {
            if (nums[end] === 0) zerosCount++;
            if (zerosCount > k) break;
            maxLength = Math.max(maxLength, end - start + 1);
        }
    }
    return maxLength;
}

// Test
console.log(longestOnes([1,1,1,0,0,0,1,1,1,1,0], 2)); // Output: 6

Line Notes

let maxLength = 0;Initialize max length to track longest valid subarray

for (let start = 0; start < n; start++)Outer loop picks start index

let zerosCount = 0;Reset zero count for each new start

if (nums[end] === 0) zerosCount++;Count zeros in current subarray

if (zerosCount > k) break;Stop if zero count exceeds k

maxLength = Math.max(maxLength, end - start + 1);Update max length if valid

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, counting zeros inside inner loop leads to O(n^2) time.

💡 For n=1000, this means up to 1,000,000 operations, which is slow for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

🧠

Sliding Window with Two Pointers

💡 This approach uses two pointers to maintain a window with at most k zeros, improving efficiency by avoiding repeated counting.

Intuition

Expand the right pointer to include elements, and move the left pointer to shrink the window when zeros exceed k, tracking the max window size.

Algorithm

1. Initialize left pointer and zero count to 0.
2. Expand right pointer through the array.
3. Increment zero count when a zero is encountered.
4. If zero count exceeds k, move left pointer right until zero count ≤ k.
5. Update max length with the current window size.

💡 The key is dynamically adjusting the window size to maintain the zero count constraint efficiently.

</>

Code

def longestOnes(nums, k):
    left = 0
    zeros_count = 0
    max_length = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zeros_count += 1
        while zeros_count > k:
            if nums[left] == 0:
                zeros_count -= 1
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    print(longestOnes([1,1,1,0,0,0,1,1,1,1,0], 2))  # Output: 6

Line Notes

left = 0Initialize left pointer of the sliding window

zeros_count = 0Track number of zeros in current window

for right in range(len(nums))Expand right pointer to include new elements

if nums[right] == 0Increment zero count when zero encountered

while zeros_count > kShrink window from left if zero count exceeds k

if nums[left] == 0Decrement zero count when removing zero from window

max_length = max(max_length, right - left + 1)Update max length with current valid window size

public class Solution {
    public static int longestOnes(int[] nums, int k) {
        int left = 0, zerosCount = 0, maxLength = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) zerosCount++;
            while (zerosCount > k) {
                if (nums[left] == 0) zerosCount--;
                left++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,0,0,0,1,1,1,1,0};
        System.out.println(longestOnes(nums, 2)); // Output: 6
    }
}

Line Notes

int left = 0, zerosCount = 0, maxLength = 0;Initialize pointers and counters

for (int right = 0; right < nums.length; right++)Expand right pointer through array

if (nums[right] == 0) zerosCount++;Count zeros in current window

while (zerosCount > k)Shrink window from left if zero count exceeds k

if (nums[left] == 0) zerosCount--;Decrement zero count when removing zero

maxLength = Math.max(maxLength, right - left + 1);Update max length with current window size

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestOnes(vector<int>& nums, int k) {
    int left = 0, zerosCount = 0, maxLength = 0;
    for (int right = 0; right < (int)nums.size(); right++) {
        if (nums[right] == 0) zerosCount++;
        while (zerosCount > k) {
            if (nums[left] == 0) zerosCount--;
            left++;
        }
        maxLength = max(maxLength, right - left + 1);
    }
    return maxLength;
}

int main() {
    vector<int> nums = {1,1,1,0,0,0,1,1,1,1,0};
    cout << longestOnes(nums, 2) << endl; // Output: 6
    return 0;
}

Line Notes

int left = 0, zerosCount = 0, maxLength = 0;Initialize sliding window pointers and zero count

for (int right = 0; right < (int)nums.size(); right++)Expand right pointer over array

if (nums[right] == 0) zerosCount++;Increment zero count when zero encountered

while (zerosCount > k)Shrink window from left if zero count exceeds k

if (nums[left] == 0) zerosCount--;Decrement zero count when removing zero from window

maxLength = max(maxLength, right - left + 1);Update max length with current window size

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

// Test
console.log(longestOnes([1,1,1,0,0,0,1,1,1,1,0], 2)); // Output: 6

Line Notes

let left = 0, zerosCount = 0, maxLength = 0;Initialize pointers and zero count

for (let right = 0; right < nums.length; right++)Expand right pointer through array

if (nums[right] === 0) zerosCount++;Count zeros in current window

while (zerosCount > k)Shrink window from left if zero count exceeds k

if (nums[left] === 0) zerosCount--;Decrement zero count when removing zero

maxLength = Math.max(maxLength, right - left + 1);Update max length with current window size

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is visited at most twice by left and right pointers, leading to linear time.

💡 For n=100,000, this means about 200,000 operations, which is efficient for large inputs.

Interview Verdict: Accepted

This approach is optimal and efficient, suitable for large inputs and interview coding.

🧠

Sliding Window with Count of Zeros Using Queue

💡 This approach uses a queue to store zero indices to efficiently track and move the left pointer, providing an alternative to counting zeros manually.

Intuition

Keep track of zero positions in a queue. When zeros exceed k, move left pointer to the position after the oldest zero.

Algorithm

1. Initialize a queue to store indices of zeros.
2. Expand right pointer through the array.
3. When a zero is found, add its index to the queue.
4. If queue size exceeds k, move left pointer to one past the oldest zero index.
5. Update max length with current window size.

💡 This method explicitly tracks zeros, making it easier to adjust the window when zero flips exceed k.

</>

Code

from collections import deque

def longestOnes(nums, k):
    zero_positions = deque()
    left = 0
    max_length = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zero_positions.append(right)
        if len(zero_positions) > k:
            left = zero_positions.popleft() + 1
        max_length = max(max_length, right - left + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    print(longestOnes([1,1,1,0,0,0,1,1,1,1,0], 2))  # Output: 6

Line Notes

from collections import dequeImport deque for efficient zero index tracking

zero_positions = deque()Queue to store indices of zeros in current window

if nums[right] == 0Add zero index to queue when zero encountered

if len(zero_positions) > kIf zeros exceed k, move left pointer past oldest zero

left = zero_positions.popleft() + 1Update left pointer to maintain at most k zeros

max_length = max(max_length, right - left + 1)Update max length with current window size

import java.util.*;

public class Solution {
    public static int longestOnes(int[] nums, int k) {
        Deque<Integer> zeroPositions = new LinkedList<>();
        int left = 0, maxLength = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) zeroPositions.addLast(right);
            if (zeroPositions.size() > k) left = zeroPositions.pollFirst() + 1;
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,0,0,0,1,1,1,1,0};
        System.out.println(longestOnes(nums, 2)); // Output: 6
    }
}

Line Notes

Deque<Integer> zeroPositions = new LinkedList<>();Queue to track zero indices efficiently

if (nums[right] == 0) zeroPositions.addLast(right);Add zero index to queue

if (zeroPositions.size() > k) left = zeroPositions.pollFirst() + 1;Move left pointer past oldest zero if zeros exceed k

maxLength = Math.max(maxLength, right - left + 1);Update max length with current window size

int left = 0, maxLength = 0;Initialize pointers and max length

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

int longestOnes(vector<int>& nums, int k) {
    deque<int> zeroPositions;
    int left = 0, maxLength = 0;
    for (int right = 0; right < (int)nums.size(); right++) {
        if (nums[right] == 0) zeroPositions.push_back(right);
        if ((int)zeroPositions.size() > k) {
            left = zeroPositions.front() + 1;
            zeroPositions.pop_front();
        }
        maxLength = max(maxLength, right - left + 1);
    }
    return maxLength;
}

int main() {
    vector<int> nums = {1,1,1,0,0,0,1,1,1,1,0};
    cout << longestOnes(nums, 2) << endl; // Output: 6
    return 0;
}

Line Notes

deque<int> zeroPositions;Queue to store zero indices for efficient tracking

if (nums[right] == 0) zeroPositions.push_back(right);Add zero index to queue

if ((int)zeroPositions.size() > k)Check if zeros exceed allowed flips

left = zeroPositions.front() + 1;Move left pointer past oldest zero

zeroPositions.pop_front();Remove oldest zero index from queue

maxLength = max(maxLength, right - left + 1);Update max length with current window size

function longestOnes(nums, k) {
    const zeroPositions = [];
    let left = 0, maxLength = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] === 0) zeroPositions.push(right);
        if (zeroPositions.length > k) {
            left = zeroPositions.shift() + 1;
        }
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

// Test
console.log(longestOnes([1,1,1,0,0,0,1,1,1,1,0], 2)); // Output: 6

Line Notes

const zeroPositions = [];Array used as queue to track zero indices

if (nums[right] === 0) zeroPositions.push(right);Add zero index to queue

if (zeroPositions.length > k)Check if zero count exceeds k

left = zeroPositions.shift() + 1;Move left pointer past oldest zero

maxLength = Math.max(maxLength, right - left + 1);Update max length with current window size

⏱

Complexity

TimeO(n)

SpaceO(k)

Each element is processed once; queue size is at most k, so space is O(k).

💡 For large n and small k, this approach is efficient and uses minimal extra space.

Interview Verdict: Accepted

This approach is optimal and useful when explicit zero positions are needed or for clarity.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the sliding window approach (Approach 2) is the best to code for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Sliding Window with Two Pointers	O(n)	O(1)	No	Yes, by tracking pointers	Code this approach for optimal solution
3. Sliding Window with Queue	O(n)	O(k)	No	Yes, explicit zero positions tracked	Good alternative if explicit zero tracking is needed

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the sliding window approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding.Introduce the sliding window technique as an optimization.Discuss how to maintain the zero count and adjust window size.Code the sliding window solution and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to optimize from brute force to linear time, your understanding of sliding window technique, and your coding accuracy.

Common Follow-ups

• What if k is zero? → Just find longest consecutive ones.
• Can you solve it if the array is very large? → Sliding window is efficient for large inputs.
• How to modify if you want to return the subarray indices? → Track left and right pointers when max length updates.
• What if the array contains numbers other than 0 and 1? → Problem constraints limit to binary array; otherwise, approach changes.

💡 These follow-ups test your understanding of edge cases, scalability, and ability to adapt the solution.

🔍

Pattern Recognition

When to Use

1) Problem asks for longest subarray or substring, 2) Constraint on number of certain elements (like zeros), 3) Variable window size, 4) Need to optimize from brute force to linear time.

Signature Phrases

maximum number of consecutive 1'sflip at most k 0'slongest subarray with at most k zeros

NOT This Pattern When

Fixed-size sliding window problems or problems without constraints on element counts

Similar Problems

Longest Substring with At Most K Distinct Characters - similar variable window with constraintsLongest Repeating Character Replacement - similar sliding window with character replacementMax Consecutive Ones II - similar but with k=1

Practice

1. Consider the following code snippet implementing the optimal sliding window approach to check if s2 contains a permutation of s1. Given s1 = "ab" and s2 = "eidbaooo", what is the return value of the function?

easy

A. True

B. Raises an IndexError

C. False

D. Returns None

Solution

1. Step 1: Trace window expansion and counts

   For s1 = "ab", count array has counts for 'a' and 'b'. Sliding window moves over s2 = "eidbaooo". When window covers substring "ba" starting at index 3, window_count matches count, so formed == required.

2. Step 2: Confirm return value

   At this point, function returns True because a permutation of s1 is found in s2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Substring "ba" is a permutation of "ab" [OK]

Hint: Check substring "ba" matches "ab" permutation [OK]

Common Mistakes:

• Off-by-one errors in window size
• Forgetting to return True when formed == required

2. Consider the following buggy code for maxSatisfied. Which line contains the subtle bug that causes incorrect results on some inputs?

def maxSatisfied(customers, grumpy, X):
    n = len(customers)
    base_satisfied = 0
    for i in range(n):
        if grumpy[i] == 0:
            base_satisfied += customers[i]
    window_sum = 0
    for i in range(X):
        if grumpy[i] == 1:
            window_sum += customers[i]
    max_extra = window_sum
    for i in range(X, n):
        if grumpy[i] == 1:
            window_sum += customers[i]
        if grumpy[i - X] == 0:
            window_sum -= customers[i - X]
        if window_sum > max_extra:
            max_extra = window_sum
    return base_satisfied + max_extra

medium

A. Line checking if grumpy[i] == 1 before adding customers[i]

B. Line initializing base_satisfied with customers where grumpy[i] == 0

C. Line checking if grumpy[i - X] == 0 before subtracting customers[i - X]

D. Line updating max_extra when window_sum > max_extra

Solution

1. Step 1: Identify subtraction condition

   The code subtracts customers[i - X] only if grumpy[i - X] == 0, but it should subtract only if grumpy[i - X] == 1 because only grumpy customers were added.

2. Step 2: Consequence of bug

   This causes incorrect window sums, as some grumpy customers are never subtracted, inflating window_sum.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Subtraction condition must match addition condition [OK]

Hint: Check symmetry of add and subtract conditions [OK]

Common Mistakes:

• Confusing grumpy check in subtraction
• Forgetting to subtract outgoing element
• Mixing base satisfaction with window sums

3. The following code attempts to find the length of the longest substring with at most k distinct characters. Identify the bug that causes incorrect results on some inputs.

from collections import OrderedDict

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
    if k == 0 or not s:
        return 0
    left = 0
    max_length = 0
    last_seen = OrderedDict()
    for right, char in enumerate(s):
        if char in last_seen:
            del last_seen[char]
        last_seen[char] = right
        max_length = max(max_length, right - left + 1)
        if len(last_seen) > k:
            _, idx = last_seen.popitem(last=False)
            left = idx + 1
    return max_length

medium

A. Not handling the case when k is zero or string is empty

B. Deleting the character from last_seen before re-inserting it

C. Updating max_length before shrinking the window when distinct chars exceed k

D. Using OrderedDict instead of a frequency map

Solution

1. Step 1: Locate max_length update position

   max_length is updated before shrinking the window when distinct chars exceed k, so invalid windows are counted.

2. Step 2: Understand impact

   This causes max_length to include substrings with more than k distinct characters, violating constraints.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving max_length update after shrinking fixes correctness [OK]

Hint: Update max_length only after ensuring window is valid [OK]

Common Mistakes:

• Updating max_length too early before shrinking window
• Confusing order of operations in sliding window

4. The following code attempts to find the length of the longest substring without repeating characters. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line 7: left = index_map[char] + 1

B. Line 6: if char in index_map:

C. Line 5: for right, char in enumerate(s):

D. Line 9: max_len = max(max_len, right - left + 1)

Solution

1. Step 1: Identify the bug in updating left pointer

   The code updates left pointer unconditionally to index_map[char] + 1 when a duplicate is found, but does not check if this moves left backward, which can shrink the window incorrectly.

2. Step 2: Correct approach

   Update left only if index_map[char] + 1 is greater than current left to avoid moving left backward.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing boundary check on left pointer update causes wrong window size [OK]

Hint: Check if left pointer moves backward [OK]

Common Mistakes:

• Not verifying left pointer position before update
• Assuming duplicates always appear after left

5. What is the time complexity of the optimal sliding window maximum algorithm using a monotonic deque for an input array of size n and window size k?

medium

A. O(n * k)

B. O(n log k)

C. O(n)

D. O(k)

Solution

1. Step 1: Identify complexity of outer and inner loops

   The algorithm iterates over each element once (O(n)). Each element is pushed and popped at most once from the deque, so total deque operations are O(n).

2. Step 2: Check if any hidden costs exist

   No nested loops or log factors; deque operations are O(1) amortized, so total time is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Amortized deque operations ensure linear time [OK]

Hint: Each element is pushed and popped at most once [OK]

Common Mistakes:

• Assuming nested loops cause O(n*k)
• Confusing max-heap complexity with deque
• Ignoring amortized cost of deque operations