Advertisement
kai-rocket

Max Consecutive Ones III

Mar 26th, 2021
762
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.73 KB | None
  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.  
Advertisement
RAW Paste Data Copied
Advertisement