Sliding Window (Window - Invariant - Decision)

Sliding Window (Window - Invariant - Decision)

Mar 6, 2022ยท

2 min read

The sliding windows have a very nice common code structure. Has three main things

  1. Window
  2. Invariant - Something that needs to be true for the window to be valid
  3. Decision when invariant is met


LeetCode 219 - Contains Duplicate Within the size

  • Window: dups -> Set
  • Decision: Is there a repeating element
  • Invariant: size(window)
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        dups = set()
        for idx, elm in enumerate(nums):
            if elm in dups:
                return True
            if len(dups) > k:
        return False

Maximum SubArray Sum

  • Window: window/queue
  • Decision: maximum sum
  • Invariant: size(window)
def maximumSubArrayOfSize(arr: str, k: int) -> int:
    window = []
    max_sum = 0
    for elm in arr:
        while len(window) > k:
        max_sum = max(max_sum, sum(window))
    return max_sum

LeetCode 904 - Fruit Into Baskets

  • Window: basket/window
  • Decision: maximum_no_of_elements in basket
  • Invariant: no_unique_elements(window) <= 2
import collections
class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        basket = collections.defaultdict(int)
        max_count = 0 
        window = [] 
        for fruit in fruits:
            basket[fruit] += 1

            while len(basket) > 2:
                elm = window.pop(0)
                basket[elm] -= 1
                if basket[elm] == 0:
                    del basket[elm]

            max_count = max(max_count, sum(basket.values()))
        return max_count

Though this last problem looks somewhat complicated, the complexity is around maintaining and updating three variables basket, max_count, and window. The extra variable is basket if we introduce that after common code to add and decision it is easy to worry about invariant.


Here is a Map of things we have written so far.


Also, we would like to hang with people who are doing these algorithms. Join us at Discord or follow us over Twitter/Instagram.