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
            dups.add(elm)
            if len(dups) > k:
                dups.remove(nums[idx-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:
        window.append(elm)
        while len(window) > k:
            window.pop(0)
        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
            window.append(fruit)

            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.

UpNext

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.