 # Max Consecutive Ones III

Mar 26th, 2021
762
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from collections import deque
2.
3. class Solution:
4.     def longestOnes(self, A: List[int], K: int) -> int:
5.         # Initialise longest_length to 0
6.         longest_length = 0
7.
8.         # Initialise window starting at index 0 with left_bound and right_bound
9.         left_bound = 0
10.         right_bound = 0
11.
12.         # Initialise positions of 0s to empty deque zero_indexes
13.         zero_indexes = deque([])
14.
15.         # Iteratively increase the right_bound
16.         while right_bound < len(A):
17.
18.             # When we see a 0
19.             if A[right_bound] == 0:
20.
21.                 # Enqueue that 0's position in zero_indexes
22.                 zero_indexes.append(right_bound)
23.
24.                 # If length of zero_indexes is > K:
25.                 if len(zero_indexes) > K:
26.                     # popleft from zero_indexes
27.                     first_zero_in_prev_window = zero_indexes.popleft()
28.                     # Move left bound to the first index (elem) in zero_indexes (after popping)
29.                     left_bound = first_zero_in_prev_window + 1
30.
31.                     # Move right bound to avoid double-counting the same right bound
32.                     right_bound += 1
33.
34.                     # Skip to next iteration of loop because longest_length can't have increased
35.                     continue
36.
37.             # Update longest_length
38.             curr_window_size = right_bound - left_bound + 1
39.             longest_length = max(longest_length, curr_window_size)
40.
41.             # Increment right bound to continue traversal
42.             right_bound += 1
43.
44.         # Return longest length detected
45.         return longest_length
46.