1004. Max Consecutive Ones III

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6

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 <= 10^5 nums[i] is either 0 or 1. 0 <= k <= nums.length

Solution Approach

The solution uses a sliding window technique to maintain a window with at most k zeros, expanding the window by moving the right pointer and shrinking it by moving the left pointer when the number of zeros exceeds k, thereby finding the maximum length of consecutive 1s.

Algorithm

1. Use a sliding window to traverse the array while keeping track of the number of zeros within the window.
2. If the number of zeros exceeds k, move the left pointer to the right to reduce the window size until the number of zeros is within the limit.
3. Continuously update the maximum length of the window to get the longest sequence of consecutive 1s that can be achieved by flipping at most k zeros.

Implement

    class Solution:
  def longestOnes(self, nums: List[int], k: int) -> int:
      # l, r   while r == 0 and zero > k: l += 1  
      # zero == k  max res, r - l + 1
      l, r = 0, 0
      n = len(nums)
      ct_zero = 0
      res = 0
      while r < n:
          if nums[r] == 0:
              ct_zero += 1
              while ct_zero > k:
                  if nums[l] == 0:
                      ct_zero -= 1
                  l += 1
          res = max(res, r - l + 1)
          r += 1
      return res

    
    

Twitter  facebook  Email