Max Consecutive Ones III

mediumSliding Window53 stepsJava · Python · C++

Find the longest run of 1s if you may flip at most k zeros. Grow the window to the right counting zeros inside it; whenever there are more than k, shrink from the left until there are k again.

▶ Watch the animated trace

Traced input: nums = [1, 1, 0, 0, 1, 1, 1, 0, 1], k = 2 → 7. Original problem: neetcode.io/problems/max-consecutive-ones-iii

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(1)

Each index enters and leaves the window at most once.

Key idea

Reframe: the longest window containing at most k zeros.
Expand r; if nums[r] is 0, increase zeros.
While zeros > k, move l right, decreasing zeros when a 0 leaves.
Every valid window is a candidate answer.

Common mistakes

Actually flipping values in the array.
Shrinking with if instead of while (fine only in the non-shrinking variant).
Forgetting k = 0, where the answer is the longest run of 1s.

Solution

Java

int longestOnes(int[] nums, int k) {
    int l = 0, zeros = 0, best = 0;
    for (int r = 0; r < nums.length; r++) {
        if (nums[r] == 0) zeros++;
        while (zeros > k) {
            if (nums[l] == 0) zeros--;
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Python

def longestOnes(nums: List[int], k: int) -> int:
    l = zeros = best = 0
    for r, x in enumerate(nums):
        if x == 0: zeros += 1
        while zeros > k:
            if nums[l] == 0: zeros -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

C++

int longestOnes(vector<int>& nums, int k) {
    int l = 0, zeros = 0, best = 0;
    for (int r = 0; r < (int)nums.size(); r++) {
        if (nums[r] == 0) zeros++;
        while (zeros > k) {
            if (nums[l] == 0) zeros--;
            l++;
        }
        best = max(best, r - l + 1);
    }
    return best;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
k = 0 No flips: the longest plain run of 1s.	`nums = [1, 0, 1, 1, 0], k = 0`	`2`
All zeros Only two zeros can be flipped.	`nums = [0, 0, 0], k = 2`	`2`
k larger than zeros Flip everything; the whole array.	`nums = [0, 1, 0], k = 5`	`3`
All ones No zeros to flip.	`nums = [1, 1, 1], k = 1`	`3`