Max Consecutive Ones III

1. The obvious way

   Try every sub-list and count its zeros: O(n²).

2. The key insight

   A window is fixable when it contains at most k zeros. Extend on the right; whenever the zero count passes k, move the left edge forward until the count is back to k (a zero leaving gives a spare back). The window length at every step is a candidate answer.

3. The algorithm
   1. Zero count = 0, left edge at the start, best = 0.
   2. Take the next number on the right; if it is 0, zero count + 1.
   3. Zero count above k? Move the left edge forward (subtract a zero when you pass one) until it is k again.
   4. Best = the longest window length seen.

Watch it run

zeros used 2, best 5

def longest_ones(nums, k):
    left = 0
    zeros = 0                                # spares currently in use
    best = 0
    for right, number in enumerate(nums):
        if number == 0:
            zeros += 1
        while zeros > k:                     # out of spares: shrink from the left
            if nums[left] == 0:
                zeros -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.