Medium

Max Consecutive Ones III

057

Return the longest subarray containing only 1s after flipping at most k zeros.

EXAMPLES

Example 1

Input
{
  "nums": [
    1,
    1,
    1,
    0,
    0,
    0,
    1,
    1,
    1,
    1,
    0
  ],
  "k": 2
}

Output
6

FUNCTION SHAPE

nums: intArrayk: int→int

SOLUTION NOTE

In this case, our window is not a frequency map, rather an integer. num_0 represents the frequency of 0's in our window. When it is > k, this means we can no longer flip all the 0's in the window, so this is invalid.

Reveal reference solution +

pythonREFERENCE

def longestOnes(self, nums: List[int], k: int) -> int:
    n, l, num_0, res = len(nums), 0, 0, 0

    for r in range(n):
        num_0 += nums[r] == 0

        while num_0 > k:
            num_0 -= nums[l] == 0
            l += 1

        res = max(res, r - l + 1)

    return res

TimeO(n)

SpaceO(1)

Open on LeetCode ↗