VitaminAlgo

VitaminAlgo

Sliding Window (Window - Invariant - Decision)

Sliding Window (Window - Invariant - Decision)

Anup Kalburgi's photo
Anup Kalburgi
ยทMar 6, 2022ยท

2 min read

Table of contents

  • LeetCode 219 - Contains Duplicate Within the size
  • Maximum SubArray Sum
  • LeetCode 904 - Fruit Into Baskets

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

image.png

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.

image.png

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

ย 
Share this