Log inSign up
mediumLeetCodeNot Started

Max Consecutive Ones III

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

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] - Bold numbers were flipped from 0 to 1. The longest subarray is 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: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] - 3 zeros were flipped. The longest subarray is length 10.

Example 3:

Input: nums = [0,0,0,0], k = 0
Output: 0
Explanation: No zeros can be flipped, and there are no 1s, so 0.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Sliding Window & Two Pointers technique
  • Max Consecutive Ones basics
  • Subarray length calculation right - left + 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the budget-based sliding window pattern for binary array flips.
  • Understand why at most K flips is equivalent to finding a subarray with at most K zeros.
  • Implement both standard shrinking sliding window and non-shrinking lazy sliding window.
  • Handle edge cases like k = 0, all 0s, and all 1s.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Longest subarray of 1s with at most K flips or modifications.
  • Binary array where contiguous consecutive 1s are maximized.
  • Dynamic budget constraint tracking counts of 0s.

Algorithmic Decision Tree:

  • If checking all subarrays -> O(N2) brute force (times out).
  • If finding longest contiguous window with at most K zeros -> Sliding Window in O(N).
  • If k == 0 -> Standard Max Consecutive Ones.

Connected Patterns:

Longest Repeating Character ReplacementLongest Subarray of 1s After Deleting One ElementFruit Into Baskets

1. Brute Force (Nested Loop with Zero Counter)

Intuition

Try every possible starting index i. Expand rightwards with index j. Count how many zeros appear. If zeros <= k, record length j - i + 1. Update max length.

Algorithm

  1. Step 1: Initialize maxLen = 0.
  2. Step 2: For each i from 0 to n - 1:
  3. - Initialize zeros = 0.
  4. - For each j from i to n - 1:
  5. - If nums[j] == 0, zeros++.
  6. - If zeros > k, break.
  7. - maxLen = max(maxLen, j - i + 1).
  8. Step 3: Return maxLen.

Brute Force (Nested Loop with Zero Counter) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 1, 1, 0, 0, 0]
Current operationSTEP 1 OF 6
Phase 1 — Window Initialization: Both left and right pointers anchor at index 0
Visual state
Values and pointers at this exact step
pointers
S
1
1
1
0
0
0
0
↑ L↑ R
1
2
3
4
5
Variables at this step
L Pointer
0
R Pointer
0
Window Value
1
Window Length
1
Best Metric
Evaluating...
Check / comparison
Current element arr[0]=1. Window span [0..0].
Decision / next transition
Initialize window state and evaluate target constraint.
Why this step matters

Phase 1 — Window Initialization: Both left and right pointers anchor at index 0. Initial window length is 1 with sum/metric=1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 int longestOnes(std::vector<int>& nums, int k) {
8 int n = nums.size();
9 int maxLen = 0;
10
11 for (int i = 0; i < n; i++) {
12 int zeros = 0;
13 for (int j = i; j < n; j++) {
14 if (nums[j] == 0) zeros++;
15 if (zeros > k) break;
16 maxLen = std::max(maxLen, j - i + 1);
17 }
18 }
19 return maxLen;
20 }
21};
22
23int main() {
24 Solution sol;
25 std::vector<int> nums = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
26 std::cout << "Max 1s: " << sol.longestOnes(nums, 2) << std::endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force (Nested Loop with Zero Counter).
  • Space complexity: O(1) — Space complexity for Brute Force (Nested Loop with Zero Counter).

Why Brute Force Doesn't Scale:

For N = 100,000, N2 = 1010 operations (over 10 seconds). The two-pointer sliding window guarantees linear time O(N), processing 100,000 elements in < 5 milliseconds.

With N = 100,000: Brute force takes ~10 billion operations; Sliding window completes in ~200,000 operations (~50,000x faster).

2. Better (Standard Sliding Window with Shrink While Loop)

Intuition

Expand right pointer. When nums[right] == 0, increment zeroCount. While zeroCount > k, increment left and decrement zeroCount if nums[left] was 0. Update maxLen at each step with right - left + 1.

Algorithm

  1. Step 1: Initialize left = 0, zeros = 0, and maxLen = 0.
  2. Step 2: For each right from 0 to n - 1:
  3. - If nums[right] == 0, zeros++.
  4. - While zeros > k:
  5. - If nums[left] == 0, zeros--.
  6. - left++.
  7. - maxLen = max(maxLen, right - left + 1).
  8. Step 3: Return maxLen.

Standard Sliding Window on [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1
Visual state
Values and pointers at this exact step
array
S
nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2
0
↑ i (Step 1)
Variables at this step
Current Phase
1
Inspected Value
nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2
Condition Met
false
Running Status
Evaluating
Why this step matters

Phase 1 — Step 1: Step 1

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class Solution {
6public:
7 int longestOnes(std::vector<int>& nums, int k) {
8 int left = 0;
9 int zeros = 0;
10 int maxLen = 0;
11
12 for (int right = 0; right < (int)nums.size(); right++) {
13 if (nums[right] == 0) {
14 zeros++;
15 }
16
17 while (zeros > k) {
18 if (nums[left] == 0) {
19 zeros--;
20 }
21 left++;
22 }
23 maxLen = std::max(maxLen, right - left + 1);
24 }
25 return maxLen;
26 }
27};
28
29int main() {
30 Solution sol;
31 std::vector<int> nums = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
32 std::cout << "Better Max 1s: " << sol.longestOnes(nums, 2) << std::endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better (Standard Sliding Window with Shrink While Loop).
  • Space complexity: O(N) — Space complexity for Better (Standard Sliding Window with Shrink While Loop).

3. Optimal (Non-Shrinking Lazy Sliding Window)

Intuition

We only care about the MAXIMUM window length. When an invalid element enters (zeros > k), we do not loop to shrink; we simply shift left forward by 1 (and decrement zero count if nums[left] == 0). The window never shrinks, and at the end of the array, the maximum window size is simply nums.length - left.

Algorithm

  1. Step 1: Initialize left = 0, zeros = 0, and n = nums.length.
  2. Step 2: Loop right from 0 to n - 1:
  3. - If nums[right] == 0, increment zeros.
  4. - If zeros > k:
  5. - If nums[left] == 0, decrement zeros.
  6. - Increment left.
  7. Step 3: Return n - left.

Non-Shrinking Window on [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2]
Current operationSTEP 1 OF 6
Phase 1 — Step 1: Step 1
Visual state
Values and pointers at this exact step
array
S
nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2
0
↑ i (Step 1)
Variables at this step
Current Phase
1
Inspected Value
nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2
Condition Met
false
Running Status
Evaluating
Why this step matters

Phase 1 — Step 1: Step 1

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 int longestOnes(std::vector<int>& nums, int k) {
7 int left = 0;
8 int zeros = 0;
9 int n = nums.size();
10
11 for (int right = 0; right < n; right++) {
12 if (nums[right] == 0) {
13 zeros++;
14 }
15 if (zeros > k) {
16 if (nums[left] == 0) {
17 zeros--;
18 }
19 left++;
20 }
21 }
22 return n - left;
23 }
24};
25
26int main() {
27 Solution sol;
28 std::vector<int> nums = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
29 std::cout << "Optimal Max 1s: " << sol.longestOnes(nums, 2) << std::endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal (Non-Shrinking Lazy Sliding Window).
  • Space complexity: O(1) — Space complexity for Optimal (Non-Shrinking Lazy Sliding Window).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Subarray Search with Zero Counter)O(N^2)O(1)For each starting index i, expand j and count zeros. Stop when zeros > k. Track max length.Repeatedly scanning overlapping subarrays.
2.Better (Standard Sliding Window with Shrink While Loop)O(N)O(1)Expand right pointer. While zeros > k, shrink left pointer and decrement zeros count.Pointer adjustments.
3.Optimal (Non-Shrinking Lazy Sliding Window)OptimalO(N)O(1)Window only expands or shifts right by 1 when invalid. Never shrinks, ending with window size = max length.Single pass scan bound.

Common Pitfalls & Crucial Edge Cases

Actually mutating or flipping array values

You do not need to flip 0s to 1s in memory. Counting the number of 0s in the window is sufficient.

Resetting window to index `i + 1`

Resetting left to i + 1 causes quadratic O(N2) complexity instead of sliding.

Using `left < right` instead of `left <= right` on shrink

If k = 0 and nums[right] = 0, left must advance past right to maintain zeros = 0.

Crucial Edge Cases to Validate:

  • k = 0 (nums = [1, 0, 1, 1, 0, 1], k = 0): No zeros can be flipped; reduces to standard maximum contiguous 1s.
  • k >= total zeros in array (nums = [0, 1, 0, 1], k = 2): All zeros can be flipped; returns n.
  • All 0s (nums = [0, 0, 0, 0], k = 2): Returns k.
  • All 1s (nums = [1, 1, 1, 1], k = 2): Returns n.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the problem transformation immediately: "This is equivalent to finding the longest subarray containing at most K zeros."
  2. Highlight that space complexity is O(1) and time complexity is O(N) because each element enters and exits the window at most once.
  3. Mention the non-shrinking sliding window variant as an advanced optimization.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is "flipping at most K zeros" equivalent to finding the longest subarray with at most K zeros?

2.What is the time complexity of the Two-Pointer Sliding Window approach?

3.What is the space complexity of the optimal sliding window approach?

Back to DSA Sheet