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

- Window
- Invariant - Something that needs to be true for the window to be valid
- 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.

ย