Max Consecutive Ones III

Description

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

Example 1:
Input: nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2
Output: 6
Explanation: Flip the two 0s at indices 5 and 10 (or 3 and 4, etc.).
Result: [1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]. The longest run of 1s is from index 5 to 10 = 6.

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
Explanation: Flip 0s at indices 4, 5, and 9.
Result: [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]. Longest run from index 2 to 11 = 10.

Example 3:
Input: nums = [1, 1, 1, 1], k = 0
Output: 4
Explanation: No flips needed, all 1s already.

Constraints

1 <= nums.length <= 10^5
nums[i] is either 0 or 1
0 <= k <= nums.length

Signature

def solution(nums: list[int], k: int) -> int: ...

Complexity

Time: O(n)
Space: O(1)

Hints

Pattern: Sliding window with constraint on zeros count
Approach: Expand right pointer, count zeros. When zeros > k, shrink from left until zeros <= k. Track max window length.
Complexity: Maintain window with at most k zeros, track maximum window size

Solutions

Python

def solution(nums, k):
    length = 0
    count = 0
    left = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            count += 1

        while count > k:
            if nums[left] == 0:
                count -= 1
            left += 1

        length = max(length, right - left + 1)

    return length