# Sliding Window (Window - Invariant - Decision)

Mar 6, 2022ยท

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:
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

• Invariant: no_unique_elements(window) <= 2
``````import collections
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
max_count = 0
window = []
for fruit in fruits:
window.append(fruit)

elm = window.pop(0)

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.