Sliding Window: Fixed-Size Template
Give a template for a fixed-size sliding window.
Answer
def fixed_sliding_window(arr, k):
curr_state = ... # relevant info about current window
answer = ... # final result
left = 0
for right in range(len(arr)):
# update window state with the new rightmost element
...
# when window size reaches k
if right - left + 1 == k:
# update best answer using current window
answer = ...
# shrink window state from the left
...
left += 1
return answerExample: maximum sum of a subarray of size $k$ (same template).
def max_sum_subarray_size_k(arr, k):
curr_sum = 0
answer = float("-inf")
left = 0
for right in range(len(arr)):
curr_sum += arr[right]
if right - left + 1 == k:
answer = max(answer, curr_sum)
curr_sum -= arr[left]
left += 1
return answer