Problem Statement in English

You’re given a binary array nums and an integer k. You can flip at most k 0’s to 1’s.

Return the maximum number of consecutive 1’s in the array if you can flip at most k 0’s.

Approach

We can use the sliding window approach here.

We maintain a window and keep track of how many 0’s we have in that window.

If the number of 0’s exceeds k, we shrink the window from the left until we have at most k 0’s in the window.

We keep track of the maximum size of the window that we can achieve with at most k 0’s.

And we’re done!

Solution in Python


class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = 0
        res = 0

        for r in range(len(nums)):
            if nums[r] != 1:
                k -= 1

            while k < 0:
                if nums[l] != 1:
                    k += 1
                l += 1
            
            res = max(res, r - l + 1)

        return res

Complexity

  • Time: $O(n)$
    Since we’re just iterating through the array once.

  • Space: $O(1)$
    Since we use a couple extra variables.

And we are done.