1004. Max Consecutive Ones III | 1656

 1class Solution:
 2    def longestOnes(self, nums: List[int], k: int) -> int:
 3        # sliding window
 4        # first extend with k zeros to ones
 5        # extend one more and we now shrink until the oldest flip
 6        # can keep track of the oldest flip with a heap
 7        # actually a deque works better time complexity-wise
 8
 9        flips = deque([])
10
11        n = len(nums)
12        l = 0
13        r = 0
14        max_len = k
15
16        while r < n and len(flips) < k:
17            if nums[r] == 0:
18                flips.append(r)
19            r += 1
20
21        if r == n:
22            return n
23
24        while r < n and nums[r] == 1:
25            r += 1
26
27        if r == n:
28            return n
29
30        r -= 1
31        # [l, 1, 1, ..., 1, r]
32        # flip_cnt == k
33        cur_len = r - l + 1
34        if cur_len > max_len:
35            max_len = cur_len
36
37        while r < n - 1:
38            r += 1
39            if nums[r] == 0:
40                flips.append(r)
41                l = flips.popleft() + 1
42            cur_len = r - l + 1
43            if cur_len > max_len:
44                max_len = cur_len
45
46        return max_len