1004. Max Consecutive Ones III Medium

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 length 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: [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 length 10.

Approach

Input: A binary array nums and an integer k max flipped zeroes.

Output: The longest number of consecutive 1s that can be formed by flipping at most k 0s.

This problem is a classic Variable-length Sliding Window type.

We can use two pointers to maintain a sliding window, keeping track of the count of 0s within it. As long as the number of 0s doesn't exceed k, the current window remains valid, and we just update our record of the max consecutive 1s. If the count exceeds k, we simply move the left pointer forward to shrink the window incrementally until the limit goes back down to k or below.

Throughout this process, as we advance the right pointer, we dynamically adjust the window side constraints while tracking the maximum legal window length, returning it all at the end.

Implementation

python

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = 0  # Left pointer
        count = 0  # Count of 0's in the current window
        ans = 0    # Maximum length sequence discovered

        for r in range(len(nums)):
            if nums[r] == 0:
                count += 1  # Increment sequence zero count

            # If we've eclipsed k permitted 0s, shrink the window bounds using left pointer
            while count > k:
                if nums[l] == 0:
                    count -= 1
                l += 1

            # Assert and upkeep max window dimensions 
            ans = max(ans, r - l + 1)

        return ans

javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function(nums, k) {
    let left = 0;
    let ans = 0;

    let count = 0;
    for (let right in nums) {
        if (nums[right] == 0) {
            count++;
        }

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

        ans = Math.max(ans, right - left + 1);
    }

    return ans;
};

Complexity Analysis

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

Links

1004. Max Consecutive Ones III (English)1004. 最大连续1的个数 III (Chinese)