Max Consecutive Ones III

Intuition

Since flipping a zero is what costs us, a window is achievable exactly when it holds at most k zeros. We slide a right pointer forward and count the zeros currently inside the window. As long as that count stays within k the window is feasible and we can extend it. When adding a new zero pushes the count above k, we advance the left pointer, discarding elements until we have dropped one zero and are back within budget. The widest window we ever observe is the answer, and because both pointers only move forward the algorithm is linear.

Algorithm walkthrough

1. 1Initialize left at 0, a zeros counter at 0, and best at 0.
2. 2Move the right pointer across the array; each time nums[right] is 0, increment zeros.
3. 3If zeros exceeds k, shrink from the left: while the count is too high, if nums[left] is 0 decrement zeros, then advance left.
4. 4After restoring the budget, the window from left to right contains at most k zeros and is therefore achievable.
5. 5Update best with the current window width right - left + 1.
6. 6When the right pointer finishes, return best.

Implementation

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0
        zeros = 0
        best = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                zeros += 1
            while zeros > k:
                if nums[left] == 0:
                    zeros -= 1
                left += 1
            best = max(best, right - left + 1)
        return best