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.