LeetCode · #1004

Max Consecutive Ones III Solution

Given a binary array nums and an integer k, return the maximum number of consecutive 1s you can obtain if you may flip at most k zeroes.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #1004

🏗️

Pattern

Sliding Window — at most k bad elements

This is a classic longest valid window problem. A window is valid if it contains at most k zeroes, because those are exactly the positions we can flip to ones. So the job becomes: find the longest subarray with at most k zeroes.

Example 1

 Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6 // Flip two zeroes to get a run of six 1s 

Example 2

 Input: nums = [0,0,1,1,1,0,0], k = 0 Output: 3 // No flips allowed → longest natural run of ones 

Constraints

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

Section Two · Approach 1

Brute Force — Expand from Every Start

For each starting index, extend the subarray rightward and count how many zeroes appear. As long as the zero count stays within k, the window is valid and can update the answer. Once zeroes exceed k, we can stop extending from that start.

Problem: This still repeats a lot of work. If we already know a large valid window, restarting from the next start index throws away useful state. Sliding window keeps the zero count and moves both ends forward only once.

Java — Expand from each start

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

Python — Expand from each start

 class Solution:
def longestOnes(self, nums: list[int], k: int) -> int:
        best = 0 for start in range(len(nums)):
            zeroes = 0 for end in range(start, len(nums)):
if nums[end] == 0:
                    zeroes += 1 if zeroes > k:
break
best = max(best, end - start + 1)
return best

Metric	Value
Time	O(n²)
Space	O(1)

Section Three · Approach 2

Sliding Window — Longest Valid Window

Maintain a window [left, right] and count how many zeroes it currently contains. Expand right every step. If the zero count becomes greater than k, shrink from the left until the window is valid again. The answer is the maximum valid window length seen.

💡 Mental model: Imagine you can afford to keep at most k broken bulbs inside a display case. As you extend the case to the right, each new bulb enters. If too many broken bulbs accumulate, you slide the left edge forward until the case is affordable again. The widest affordable case is the answer.

Algorithm

Step 1: Initialize left = 0, zeroes = 0, and best = 0.
Step 2: For each right, if nums[right] == 0, increment zeroes.
Step 3: While zeroes > k, shrink from the left. If nums[left] == 0, decrement zeroes.
Step 4: After the window is valid again, update best = max(best, right - left + 1).

🎯 Pattern to remember:

Problems of the form “longest subarray with at most K bad elements” almost always use this exact template.
The only thing that changes is what counts as “bad” — here it is a zero.

Section Four · Trace

Visual Walkthrough

Trace through nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2:

Keep at most 2 zeroes inside the window

Section Five · Implementation

Code — Java & Python

Java — Sliding window with zero counter

 class Solution {
public int longestOnes(int[] nums, int k) {
int left = 0;
int zeroes = 0;
int best = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) zeroes++;
while (zeroes > k) {
if (nums[left] == 0) zeroes--;
                left++;
            }

            best = Math.max(best, right - left + 1);
        }
return best;
    }
}

Python — Sliding window with zero counter

 class Solution:
def longestOnes(self, nums: list[int], k: int) -> int:
        left = 0
zeroes = 0
best = 0 for right in range(len(nums)):
if nums[right] == 0:
                zeroes += 1 while zeroes > k:
if nums[left] == 0:
                    zeroes -= 1
left += 1
best = max(best, right - left + 1)
return best

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Expand from each start	O(n²)	O(1)	Simple but repeats zero-count work
Sliding window ← optimal	O(n)	O(1)	Each index enters and leaves the window once

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
k = 0	`[1,1,0,1], k=0`	No flips allowed — answer is longest natural run of ones.
Enough flips for all zeroes	`[0,1,0,1], k=2`	Whole array becomes valid.
All ones	`[1,1,1], k=1`	Answer is array length.
All zeroes	`[0,0,0], k=2`	Best answer is limited by how many zeroes we can flip.
Single element	`[0], k=1`	Smallest non-trivial case.

⚠ Common Mistake: Trying to actually flip bits in the array. You do not need to modify nums at all. Just count how many zeroes are inside the current window and enforce zeroes ≤ k.

← Back to Sliding Window problems

LearningTree

LC 1004 · Max Consecutive Ones III — Solution & Explanation | DSA Guide