1004. Max Consecutive Ones III

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: [1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

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: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Constraints:

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

From: LeetCode
Link: 1004. Max Consecutive Ones III

Solution:

Ideas:

• Use a sliding window [left…right] that always contains at most k zeros.

• Expand right; when you include a 0, increment zeros.

• If zeros > k, move left forward until the window becomes valid again.

• Track the maximum window length seen (best).

Code:

int longestOnes(int* nums, int numsSize, int k) {
    int left = 0;
    int zeros = 0;
    int best = 0;

    for (int right = 0; right < numsSize; right++) {
        if (nums[right] == 0) zeros++;

        while (zeros > k) {
            if (nums[left] == 0) zeros--;
            left++;
        }

        int len = right - left + 1;
        if (len > best) best = len;
    }

    return best;
}