Coding Pattern:
Sliding Window
This pattern has an earnable cheat sheet.
Pattern concept
Step 1 of 21
![Sliding Window Slide 8: Given [2, 4, 6, 3, 1, 10], find the shortest contiguous sublist that sums up to exactly 10. Sometimes instead of using a fixed sized window, we need a dynamically sized window.](/slides/sliding-window/0_6.drawio.svg)
Use ← → arrow keys
Code snippets
# Find the sum of all of the given list's contiguous sublists
# with a length of 3.
def sum_of_fixed_sublists(nums): if len(nums) < 3:
return 0
window_sum = sum(nums[:3]) # Same as nums[0] + nums[1] + nums[2]
total_sum = window_sum
for i in range(1, len(nums) - 2):
# Remove old value and add new value to the window sum.
window_sum = window_sum - nums[i - 1] + nums[i + 2]
total_sum += window_sum
return total_sum
# Find the shortest contiguous sublist that sums up to 10.
def shortest_of_dynamic_sublists(nums): a, b, window_sum, shortest = 0, 0, 0, None
while a < len(nums):
# Expand the window until the its sum is at least 10.
while window_sum < 10 and b < len(nums):
window_sum += nums[b]
b += 1
# Check if we should save the window length.
if window_sum == 10 and (shortest is None or b - a < shortest):
shortest = b - a
# Contract the window.
window_sum -= nums[a]
a += 1
return shortest
How to identify
Does the problem involve any of these?
- Finding a contiguous subarray or substring that fulfills certain requirements
- Shortest Length Subarray Sum: Subarray that has a certain sum.
- Longest Substring Without Repeats: Substring that has no repeats.
- Fruit into Basket: Longest subarray with two distinct elements.
- Minimum Window Substring: Shortest substring that contains all characters in another string.
Note
Most sliding window problems can be solved in O(n) time since they can be solved efficiently by updating the window instead of recomputing all elements.