1004. Max Consecutive Ones III - Explanation

Description

You are 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: The subarray from indices 5 to 10 has 2 zeroes and we can flip them.

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

Constraints:

1 <= nums.length <= 100,000
nums[i] is either 0 or 1.
0 <= k <= nums.length

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        res = 0
        for l in range(len(nums)):
            cnt, r = 0, l
            while r < len(nums):
                if nums[r] == 0:
                    if cnt == k:
                        break
                    cnt += 1
                r += 1
            res = max(res, r - l)
        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Binary Search + Prefix Sum

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        prefix = [0]
        for num in nums:
            prefix.append(prefix[-1] + (1 if num == 0 else 0))
        
        res = 0
        for l in range(len(nums)):
            low, high = l, len(nums)
            while low < high:
                mid = (low + high) // 2
                if prefix[mid + 1] - prefix[l] <= k:
                    low = mid + 1
                else:
                    high = mid
            res = max(res, low - l)
        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Sliding Window

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l = res = 0
        for r in range(len(nums)):
            k -= (1 if nums[r] == 0 else 0)
            while k < 0:
                k += (1 if nums[l] == 0 else 0)
                l += 1
            res = max(res, r - l + 1)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$