Max Consecutive Ones III
A medium Sliding Window interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Sliding Window
- Sheets
- 1
- Core for
- 6 roles
The problem
Given a binary array and an integer k, find the maximum number of consecutive 1s if you can flip at most k zeros.
Example 1
- Input
- nums = [1,0,1,1,0,0,1,1,0,1], k = 2
- Output
- 6
- Why
- Flipping the two zeros at indices 4 and 5 joins 1,1 and 1,1 into a run of six ones.
Example 2
- Input
- nums = [0,1,1,0,1,0,0,1,1,1,0,1,0], k = 3
- Output
- 9
- Why
- Indices 1 to 9 hold exactly three zeros; flipping them gives nine ones in a row.
Constraints
- 1 <= nums.length <= 10^5
- nums[i] is 0 or 1
- 0 <= k <= nums.length
How to think about it
Updated 2026-09-29Flipping at most k zeros into ones is identical to finding the longest contiguous subarray that contains at most k zeros. Once translated to counting zeros rather than modifying values, the problem reduces to maintaining a window where the zero count never exceeds the budget.
Approaches, worst first
Brute force search
time O(n^2) · space O(1)
Check every subarray, count zeros, and track the maximum length among those with at most k zeros. Redundantly counts overlapping elements.
Dynamic sliding window
time O(n) · space O(1)
Expand right, incrementing a zero counter on encountering 0. When zero count exceeds k, advance left until a zero exits, decrementing the counter. Track the maximum span length seen.
Non-shrinking windowWrite this one
time O(n) · space O(1)
Shift both boundaries forward together whenever zeros exceed k rather than shrinking. The window size only grows and never decreases, ending with the maximum valid length achieved.
Where people lose marks · 3
- Handling k = 0 incorrectly by failing to reject zero elements immediately during expansion.
- Incrementing the zero count when nums[right] is 1, or decrementing when nums[left] is 1.
- Off-by-one calculation on the window length using right - left instead of right - left + 1.
The theory behind it
Sliding Window — the ground this problem stands on. All Sliding Window problems
What Sliding Window is
A sliding window is an adjustable magnifying lens placed over a continuous segment of a sequence. Rather than recalculating metrics for every potential subsection from scratch, the window expands rightward by absorbing fresh elements and contracts leftward to expel stale entries. Only data currently framed within the window borders contributes to the active calculation.
When to reach for it
Reach for a sliding window when a question asks for the longest, shortest, or optimal contiguous subarray or substring matching a constraint. Key signals include fixed window sizes like maximum sum across k consecutive values, or dynamic criteria like finding the shortest substring holding all target characters. If the target subset must form an unbroken continuous run, window mechanics replace repetitive segment rescanning.
How the pattern works
Maintain two boundary indices, left and right, defining the active interval alongside a running state accumulator. In each step, expand the right boundary to incorporate the incoming element into state totals. When current state violates the designated problem constraints, increment the left boundary while deducting departing values until validity is restored. Update your tracking metric, whether minimum window length or maximum score, only during valid intervals.
More Sliding Window problems
Target Roles
Core requirement for 6 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .