Problem statement

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 zeros.

Example 1

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: Flip the two zeros before the last group.

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

Constraints

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

Hints for Max Consecutive Ones III

1. Hint 1

   Maintain a window containing at most k zeros.

2. Hint 2

   When a new zero pushes the count over k, advance the left edge past a zero.

How to solve Max Consecutive Ones III

"Flip at most k zeros" is the same as "find the longest window containing at most k zeros" — you never need to decide which zeros to flip, only how many the window holds. Slide a window that maintains that invariant and track its largest size.

Approach

1. Keep a left edge l and a count of zeros inside the window.
2. Advance the right edge r, incrementing the zero count when nums[r] is 0.
3. While the count exceeds k, advance l, decrementing the count as it passes a zero.
4. After restoring the invariant, update the best with r - l + 1.
5. The largest window seen is the answer.

Why it works

Once the window holds at most k zeros, flipping exactly those zeros makes the whole window ones, so its length is achievable. Conversely any achievable run of ones corresponds to a window with at most k zeros, so the two quantities coincide and maximising one maximises the other. The window never needs to shrink except to restore the invariant, and each index enters and leaves once, keeping the sweep linear.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Measure the window after restoring the invariant, or you record lengths that use too many flips.
• Only decrement the zero count when the element leaving is actually a zero.
• k = 0 is legal and reduces to the longest existing run of ones.
• The window length is r - l + 1, and the answer is the maximum over all valid windows.

Reference solution

Python

from typing import List

def longestOnes(nums: List[int], k: int) -> int:
    l = 0
    zeros = 0
    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

Java

public static 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++;
        }
        if (r - l + 1 > best) 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++;
        }
        if (r - l + 1 > best) best = r - l + 1;
    }
    return best;
}

JavaScript

var longestOnes = function(nums, k) {
    let l = 0, zeros = 0, best = 0;
    for (let 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;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium