How do you solve Max Consecutive Ones III?

Use two pointers to define a sliding window. Expand the right pointer, increment zero count when encountering zeros. If zero count exceeds k, move the left pointer forward, decrementing zero count if a zero is left behind. Track the maximum window size during this process. This guarantees a single pass with O(n) time and O(1) space.

Max Consecutive Ones III

Q: What is the time complexity of Max Consecutive Ones III?

O(n). Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it, resulting in linear time.

Q: What pattern does Max Consecutive Ones III use?

The Pattern: Sliding Window (Variable Size with Constraint) The Heuristic: Maintain a window that satisfies the problem's constraint (here, at most k zeros). Expand the window greedily, and when the constraint breaks, contract from the left until the window is valid again. The maximum window size during this process is the optimal solution.

Medium Sliding Window

Problem

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.

1 ≤ nums.length ≤ 10⁵
nums[i] is 0 or 1
0 ≤ k ≤ nums.length

Example

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

Output: 6

The brute-force approach would check every subarray and count zeros, flipping up to k zeros to ones, resulting in O(n^2) time. Instead, the algorithm uses a sliding window to maintain a window with at most k zeros. It expands the right pointer, counting zeros, and when zeros exceed k, it moves the left pointer to shrink the window until zeros are again at most k. The critical moment is when the window adjusts to maintain the zero count constraint, ensuring the window always represents a valid subarray. The maximum window size recorded during this process is the answer.

Approach

Straightforward Solution

A brute-force approach would check all subarrays, count zeros, and verify if zeros <= k, resulting in O(n^2) time, which is inefficient for large inputs.

Core Observation

The problem reduces to finding the longest contiguous subarray containing at most k zeros, which can be flipped to ones to maximize consecutive ones.

Path to Optimal

Preview

Recognizing the problem as a longest subarray with at most k zeros suggests a sliding window approach. By expanding the right pointer and counting zeros, and shrinking the left pointer when zeros exceed k, the window always represents a valid subarray…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers to define a sliding window. Expand the right pointer, increment zero count when encountering zeros…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer contracts it, resulting in linear time.

Space

O(1)

Only a few integer variables are used to track pointers and zero counts, independent of input size.

Pattern Spotlight

Sliding Window (Variable Size with Constraint)

Maintain a window that satisfies the problem's constraint (here, at most k zeros). Expand the window greedily, and when the constraint breaks, contract from the left until the window is valid again. The maximum window size during this process is the optimal solution.

Solution

Python

1class Solution:
  def longestOnes(self, nums: list[int], k: int) -> int:
      left = 0
      zeros = 0
      res = 0
6
      for right, x in enumerate(nums):
          if x == 0:
              zeros += 1
10
          while zeros > k:
              if nums[left] == 0:
                  zeros -= 1
              left += 1
15
          res = max(res, right - left + 1)
17
      return res

Step-by-Step Solution

Initialize Sliding Window Pointers and Counters

3left = 0
4zeros = 0
5res = 0

Objective

To set up the initial state for the sliding window traversal, including the left pointer, zero count, and result accumulator.

Key Insight

Starting with the left pointer at zero and zero count at zero establishes the baseline for the window. The result variable tracks the maximum window size found so far. This setup is essential for the single-pass sliding window approach to work correctly.

Interview Quick-Check

Core Logic

Initialize left pointer at 0, zero count at 0, and result at 0 to prepare for window expansion and contraction.

State & Boundaries

The left pointer marks the start of the current window, and zero count tracks how many zeros are inside the window.

Expand Window and Track Zero Count

To iterate through the array with the right pointer, expanding the window and counting zeros encountered.

Contract Window to Maintain Zero Constraint

To shrink the window from the left when the zero count exceeds k, restoring the window's validity.

Update Maximum Window Size

To record the largest valid window size found during the traversal.

Return the Maximum Length of Valid Subarray

To return the computed maximum length of a subarray with at most k zeros flipped to ones.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 3 Critical

left = 0

Initialize the left pointer of the sliding window to 0.

The left pointer marks the start of the current window and is essential for controlling the window size and validity.

Line 4 Critical

zeros = 0

Initialize a counter for zeros within the current window to 0.

Tracking the number of zeros is critical to enforcing the constraint of flipping at most k zeros.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why does moving the left pointer only when zeros exceed k guarantee the longest valid window?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Max Consecutive Ones III from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Max Consecutive Ones III drill

or drill a free problem

1	`class Solution:`
2	`def longestOnes(self, nums: list[int], k: int) -> int:`
3	`left = 0`
4	`zeros = 0`
5	`res = 0`
6
7	`for right, x in enumerate(nums):`
8	`if x == 0:`
9	`zeros += 1`
10
11	`while zeros > k:`
12	`if nums[left] == 0:`
13	`zeros -= 1`
14	`left += 1`
15
16	`res = max(res, right - left + 1)`
17
18	`return res`