Sliding Window (Fixed Size)

The sliding window algorithm is used to solve problems that involve finding the maximum or minimum sum of a subarray of a fixed size. It is very similar to the Two Pointers algorithm.

Time Complexity: $O(n)$

Space Complexity: $O(k)$, where $k$ is the size of the window

Template

Python

def sliding_window(arr: list, k: int) -> int:
    window = None
    result = None

    for right in range(k, len(arr)):
        # Process window
        window = ...

        # Update result
        result = ...

    return result

Example: Maximum Sum of Subarray of Size K

Here's an example of finding the maximum sum of a subarray of size k using the sliding window technique.

• window is the sum of the current window
• result is the maximum sum of the subarray

Python

def max_sum_subarray(arr: list, k: int) -> int:
    window = sum(arr[:k])
    result = window

    for right in range(k, len(arr)):
        # Process window
        window += arr[right] - arr[right - k]

        # Update result
        result = max(result, window)

    return result