Skip to main content
Talentd

Max Consecutive Ones III - Solution & Explanation

MediumArrayBinary SearchSliding WindowPrefix Sum13 min readAsked at: Amazon, Microsoft, Goldman Sachs +17
Practice this problem

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.

 

Example 1:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

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: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

 

Constraints:

  • 1 <= nums.length <= 105
  • nums[i] is either 0 or 1.
  • 0 <= k <= nums.length

Approach Overview

Problem Overview: You get a binary array nums and an integer k. You can flip at most k zeros to ones. The goal is to return the length of the longest contiguous subarray containing only ones after performing those flips.

Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)

Check every possible subarray. For each starting index, extend the subarray to the right while counting how many zeros appear. If the zero count exceeds k, stop expanding that window. Track the maximum valid length seen. This approach works because the array is small enough to brute force in theory, but it performs up to n expansions for each starting index, leading to quadratic time. It helps you reason about the constraint: the window is valid as long as the number of zeros is ≤ k.

Approach 2: Prefix Sum + Binary Search (O(n log n) time, O(n) space)

Build a prefix sum array that stores how many zeros appear up to each index. For each right boundary, compute how many zeros exist in the window using prefix subtraction. If the count exceeds k, binary search the farthest left boundary that keeps the zero count ≤ k. This method converts the constraint into a range query problem. It’s useful when practicing prefix sum techniques combined with binary search, but the extra log factor and additional memory make it less optimal than the linear solution.

Approach 3: Sliding Window (O(n) time, O(1) space)

Maintain a window with two pointers left and right. As you expand right, track how many zeros exist in the current window. If the zero count exceeds k, move left forward until the window becomes valid again. At every step, update the maximum window length. The key insight: once a window has more than k zeros, the only fix is shrinking it from the left. Each element enters and leaves the window at most once, so the algorithm runs in linear time. This pattern is common in problems involving longest valid subarrays and is a core technique in sliding window and array optimization problems.

Recommended for interviews: The sliding window solution is the expected answer. Interviewers want to see that you recognize the "at most k constraint" and translate it into a dynamic window that expands and shrinks. Mentioning the brute force approach shows baseline reasoning, but implementing the O(n) sliding window demonstrates strong algorithmic intuition.

Approach 1: Sliding Window Approach

This approach involves using a sliding window distinguished by two pointers. The window expands by moving the right pointer and checks whether the number of zeros within the window exceeds the allowed count 'k'. If it does, we move the left pointer to shrink the window until the condition is satisfied. We aim to find the maximum window size that can be achieved following this condition.

This Python solution initializes two pointers 'left' and 'right' with 'left' starting from 0. As 'right' iterates over the array, it checks and counts zeros. If the count of zeros exceeds k, the 'left' pointer moves forward to reduce zeros count, effectively shrinking the window.

Code

PythonJavaScriptC++JavaC#C

Python

JavaScript

C++

Java

C#

C

Complexity

Time Complexity: O(n), where n is the length of the input array. Each element is processed at most twice.
Space Complexity: O(1), as no additional space is used aside from variables.

Try this approach in the editor →

Approach 2: Sliding Window

We can iterate through the array, using a variable cnt to record the current number of 0s in the window. When cnt > k, we move the left boundary of the window to the right by one position.

After the iteration ends, the length of the window is the maximum number of consecutive 1s.

Note that in the process above, we do not need to loop to move the left boundary of the window to the right. Instead, we directly move the left boundary to the right by one position. This is because the problem asks for the maximum number of consecutive 1s, so the length of the window will only increase, not decrease. Therefore, we do not need to loop to move the left boundary to the right.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

Similar problems:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Approach

Time Complexity: O(n), where n is the length of the input array. Each element is processed at most twice.
Space Complexity: O(1), as no additional space is used aside from variables.

Sliding Window—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n^2)O(1)Understanding the constraint and validating smaller inputs
Prefix Sum + Binary SearchO(n log n)O(n)When practicing prefix sum queries and binary search on ranges
Sliding WindowO(n)O(1)Optimal approach for large arrays and typical interview solution

Video Solution

L4. Max Consecutive Ones III | 2 Pointers and Sliding Window Playlist • take U forward • 371,558 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Max Consecutive Ones III easy or hard?
Max Consecutive Ones III is classified as a Medium problem. The challenge comes from recognizing that the constraint 'at most k zeros' naturally leads to a sliding window solution instead of brute-force enumeration.
How to solve Max Consecutive Ones III in O(n)?
Use a sliding window with two pointers. Expand the right pointer while counting zeros in the window. When the zero count exceeds k, move the left pointer forward until the number of zeros is at most k again. Track the maximum window size during the scan.
Max Consecutive Ones III Python or Java solution?
The logic is identical across languages. Implement a sliding window using two pointers, count zeros, shrink the window when the zero count exceeds k, and update the maximum length. FleetCode provides implementations in Python, Java, C++, JavaScript, C#, and C.
What is the best approach for Max Consecutive Ones III?
The sliding window approach is the best solution. Maintain two pointers and track how many zeros are inside the current window. If the zero count exceeds k, move the left pointer forward until the window becomes valid again. This processes each element once, giving O(n) time and O(1) space complexity.
What data structure is used in Max Consecutive Ones III?
The problem mainly uses the sliding window technique with two pointers on an array. No additional data structures are required for the optimal solution, which keeps the space complexity constant.
What is the time complexity of Max Consecutive Ones III?
The optimal sliding window solution runs in O(n) time because each element is visited at most twice—once when expanding the window and once when shrinking it. The space complexity is O(1) since only a few counters and pointers are used.
Is Max Consecutive Ones III asked at Google, Amazon, or Meta?
Max Consecutive Ones III is a common sliding window interview problem and variations of it have appeared in interviews at companies like Amazon, Google, and Meta. Interviewers use it to test understanding of two-pointer techniques and dynamic window constraints.

Ready to solve this problem?

Practice Max Consecutive Ones III with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Nice Subarray

Next

Longest Repeating Character Replacement