Sliding Window: Fixed-Size Template

Give a template for a fixed-size sliding window.

Answer
Python
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 answer

Example: maximum sum of a subarray of size $k$ (same template).

Python
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
Back to collection