1004. Max Consecutive Ones III

Medium · solved 2026-09-24 · Open on LeetCode

sliding-windowarray

Time O(n) · Space O(1)

How to get there

Read the problem as a window

“Consecutive 1’s” means a contiguous run, so the answer is the length of some subarray. Flipping at most k zeros turns a subarray into all 1’s exactly when it holds at most k zeros. So the question becomes: what is the longest subarray with at most k zeros? The code never flips anything; it counts zeros.

Two features point to a sliding window. The answer is a contiguous range, and the condition is a count kept under a limit. Growing a range can only raise its zero count, so a range over the limit stays over it as it grows. The window relies on that.

Alternatives compared

Approach	Time	Space	How it works
Brute force	O(n²)	O(1)	From each start, extend the end until the window holds k + 1 zeros.
Prefix sums + binary search	O(n log n)	O(n)	Store the zero count up to each index. The counts never decrease, so for each start a binary search finds the furthest end with at most k zeros.
Binary search on the length	O(n log n)	O(1)	If a window of length L fits, one of length L − 1 fits too. Binary-search L, checking each with a fixed-size window.
Sliding window (chosen)	O(n)	O(1)	right adds a cell; left drops cells until the window holds at most k zeros.
Non-shrinking window	O(n)	O(1)	left moves at most one step per step of right, so the window never shrinks and its final size is the answer.
Queue of zero positions	O(n)	O(k)	Keep the indices of the window’s zeros. When over k, left jumps past the oldest zero in one move.

The sliding window takes one pass and one counter, and its rule — the window holds at most k zeros after every step — is easy to check. The non-shrinking window has the same bounds, but why it is correct is harder to see. The queue replaces left’s single steps with one jump, at the cost of O(k) memory; both are O(n).

solution.py

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = zeros = best = 0
        for right, num in enumerate(nums):
            if num == 0:
                zeros += 1
            while zeros > k:
                if nums[left] == 0:
                    zeros -= 1
                left += 1
            best = max(best, right - left + 1)
        return best

Notes

Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.