< Back




1004. Max Consecutive Ones III

Another sliding window problem, however, the size of the subarray we're looking for isn't statically
defined - the window is dynamic and grows and shrinks depending upon how we satisfy the maximization
function. Our maximization function is to find a subarray that contains at most k zeroes.

To solve this, we maintain a left and right pointer for the sliding window. Also maintain a count of
zeros we've encountered as we expand the sliding window to the right. If the number of zeroes we've
encountered becomes greater than k, while the left pointer is less than or equal to the right
pointer, we shrink the window by incrementing the left pointer. During this process, we also check to
see if we've found another 0 in our subarray. If so, we decrement the count.

These two conditions, zero being less than k and shrinking the window from the left, allows us to
dynamically size the array to search for the correct subarray.

As we traverse the array, we maintain the maximum size of the subarray that satisfies our conditions.

The solution is as follows:


  class Solution:
      def longestOnes(self, nums: List[int], k: int) -> int:
          left = ans = count = 0

          for right in range(len(nums)):
              if nums[right] == 0: count += 1

              while left <= right and count > k:
                  if nums[left] == 0: count -= 1
                  left += 1

              ans = max(ans, right - left + 1)

          return ans


_ Time Complexity:

  O(n) - We traverse the array once.

_ Space Complexity:

  O(1) - No memory outside of integers are used to maintain the solution.