Max Consecutive Ones III

Leetcode Problem 1004: Max Consecutive Ones III

Problem Summary

Given a binary array nums and an integer k, return the maximum number of consecutive 1s in the array after flipping at most k zeros to ones.

Constraints:

• The array has between 1 and 100,000 elements.
• Each element is either 0 or 1.
• k is a non-negative integer up to the length of the array.

Techniques

• TODO

Solution

function longestOnes(nums: number[], k: number): number {
    let prefixSumForCountingZero = 0
    let startSubarray = 0
    let maxLength = 0

    for (let i = 0; i < nums.length; i++) {
        prefixSumForCountingZero = prefixSumForCountingZero + nums[i]

        while (prefixSumForCountingZero <= i - startSubarray - k) {
            prefixSumForCountingZero = prefixSumForCountingZero - nums[startSubarray]
            startSubarray++
        }

        maxLength = Math.max(maxLength, i - startSubarray + 1)
    }

    return maxLength
};

console.log(longestOnes([0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], 3))