Sliding Window is a computational technique that aims to reduce the use of nested loops and replace them with a single loop, thereby reducing the time complexity.
Variable Length Window
Use this pattern when you need to find a subarray that meets certain conditions, where the window size can vary.
# Processing for some subarray within nums
def variable_length_window(nums):
state = # data structure
start = 0
ans = 0
for end in range(len(nums)):
# extend window
add nums[end]
# repeatedly shrink window until its valid again
while state is not valid:
remove nums[start]
start += 1
# INVARIANT: window is valid, lets update our target
ans = max(ans, end-start+1)
return ans
Fixed Length Window
Use this pattern when you need to find or calculate something within a fixed-size subarray.
# Processing for fixed subarray within nums
def fixed_length_window(nums, k):
state = # data structure
start = 0
ans = 0
for end in range(len(nums)):
# extend window
add nums[end]
# work on window if its correct length
if end - start + 1 == k:
# INVARIANT: size of window is k here
if state is valid: update ans
# Shrink window _when_ you hit INVARIANT
remove nums[start]
start += 1
return ans
These templates can be adapted for a variety of problems, such as finding the longest substring with K distinct characters, maximum sum subarray of size K, or smallest subarray with a given sum.