Problem description:

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:

1
2
3
4
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 underlined.

Example 2:

1
2
3
4
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 underlined.

Constraints:

  • 1 <= nums.length <= 105
  • nums[i] is either 0 or 1.
  • 0 <= k <= nums.length

Solution:

Sliding window to find the range that could contain at most k 0

Count the number of 1 and add the current_zeros in the window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        start, res, cur_zero = 0, 0, 0
        cur = 0
        for end in nums:
            if end:
                cur += 1
            else:
                cur_zero += 1
                while cur_zero > k:
                    if nums[start]: 
                        cur -= 1
                    else: 
                        cur_zero -= 1
                    start += 1
            # print(start, end, cur, cur_zero)
            res = max(res, cur+cur_zero)
        return res

time complexity: $O()$
space complexity: $O()$
reference:
related problem: