Coding Interview PatternsMax Consecutive Ones III
MediumSliding Window

Max Consecutive Ones III

Explanation & Solution

Practice Problem

Description

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.

Input:nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
0
1
1
1
2
1
3
0
4
0
5
0
6
1
7
1
8
1
9
1
10
0

Output: 6

Explanation: Flip the zeros at indices 5 and 10 (or other combinations). The longest subarray of all 1's has length 6, for example [0,0,1,1,1,1,0] after flipping becomes [1,1,1,1,1,1].

Constraints

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

Approach

Sliding Window pattern

1. Initialize Variables

  • Set left = 0 as the start of the sliding window.
  • Set zeros = 0 to count the number of zeros in the current window.
  • Set maxLen = 0 to track the longest valid window found.

2. Expand the Window

  • Iterate right from 0 to nums.length - 1.
  • If nums[right] is 0, increment the zeros counter.
  • Each step grows the window by one element.

3. Shrink the Window When Too Many Zeros

  • While zeros > k, the window contains more zeros than we can flip.
  • If nums[left] is 0, decrement zeros as we remove it from the window.
  • Increment left to shrink the window from the left side.
  • Continue until zeros <= k, making the window valid again.

4. Track the Maximum Window Size

  • After ensuring the window is valid (zeros <= k), update maxLen with the current window size right - left + 1 if it is larger.

5. Return the Result

  • After processing all elements, maxLen holds the length of the longest subarray of all 1's achievable with at most k flips.

Key Insight

  • The problem is reframed as: find the longest subarray containing at most k zeros. This is a classic variable-size sliding window problem. By tracking the count of zeros in the window and shrinking when the count exceeds k, we efficiently find the optimal window without needing to try every possible combination of flips.
Time
O(n)each element is visited at most twice (once by `right`, once by `left`).
Space
O(1)only a few variables are used.

Visualization

Input:
[1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2
10111203040516171819010
—

Press ▶ or use ← → to step through

Left (L)Right (R)WindowDone
17 steps

Solution Code

Previous
Longest Substring with At Most K Distinct Characters
Next
Subarray Product Less Than K