Problem statement

https://leetcode.com/problems/max-consecutive-ones-iii/

Solution

In this problem what we actually asked is to find window of maximum size with number of zeroes no more than k. So, let us use sliding window approach with window [beg, end) and zeroes is number of zeroes in this window.

  1. If we try to add element nums[end] to our window and we still have number of zeroes <=k, we do it and move end point to the right and update zeroes and ans.
  2. In the opposite case it means that we can not extend our sliding window to the right, so we shrink it left pointer beg and again update number of zeroes inside.

Complexity

Time complexity is O(n), because beg and end in total travel 2n times. Space complexity is O(1).

Code

class Solution:
    def longestOnes(self, nums, k):
        beg, end, zeroes, ans = 0, 0, 0, 0
        while end < len(nums):
            if zeroes + (nums[end] == 0) <= k:
                zeroes += nums[end] == 0
                end += 1
                ans = max(ans, end - beg)
            else:
                zeroes -= nums[beg] == 0
                beg += 1  
        return ans