# Sliding Window Array

# Sliding Window Array

A sliding window tracks a contiguous subarray while moving its boundaries through the array. Instead of recomputing each subarray from scratch, it updates the current state when elements enter or leave the window.

You use it when the problem asks about contiguous ranges, especially fixed-size windows or variable-size windows with a constraint.

## Problem

Given an array $A$ of length $n$ and a window size $k$, find the maximum sum of any contiguous subarray of length $k$.

The window covers indices:

$$
[l, r]
$$

where:

$$
r - l + 1 = k
$$

## Algorithm

First compute the sum of the first window. Then move the window one position at a time by subtracting the element that leaves and adding the element that enters.

```id="sliding-window-max-sum"
max_window_sum(A, k):
    n = length(A)

    current = 0
    for i from 0 to k - 1:
        current += A[i]

    best = current

    for r from k to n - 1:
        current -= A[r - k]
        current += A[r]
        best = max(best, current)

    return best
```

## Example

Let

$$
A = [8, 3, 5, 1, 9]
$$

and

$$
k = 3
$$

| step | window    | sum | best |
| ---- | --------- | --: | ---: |
| 1    | [8, 3, 5] |  16 |   16 |
| 2    | [3, 5, 1] |   9 |   16 |
| 3    | [5, 1, 9] |  15 |   16 |

Return $16$.

## Correctness

The first loop computes the sum of the initial window $A[0:k]$. Each later step removes exactly the element that leaves the window and adds exactly the element that enters the window. Therefore, `current` always equals the sum of the active window.

The algorithm compares every length-$k$ window once, so `best` stores the maximum window sum.

## Complexity

| operation      | time     |
| -------------- | -------- |
| initialization | $O(k)$   |
| scan           | $O(n-k)$ |
| total          | $O(n)$   |

Space usage:

$$
O(1)
$$

## When to Use

Sliding windows are appropriate when:

* the answer depends on contiguous subarrays
* each step can update state incrementally
* the window has fixed size
* the window can grow or shrink under a constraint

They are less suitable when ranges are arbitrary and many independent queries are required. In that case, use prefix sums, Fenwick trees, or segment trees.

## Implementation

```python id="sliding-window-python"
def max_window_sum(a, k):
    if k <= 0 or k > len(a):
        raise ValueError("invalid window size")

    current = sum(a[:k])
    best = current

    for r in range(k, len(a)):
        current -= a[r - k]
        current += a[r]
        best = max(best, current)

    return best
```

```go id="sliding-window-go"
func MaxWindowSum(a []int, k int) (int, bool) {
    if k <= 0 || k > len(a) {
        return 0, false
    }

    current := 0
    for i := 0; i < k; i++ {
        current += a[i]
    }

    best := current

    for r := k; r < len(a); r++ {
        current -= a[r-k]
        current += a[r]
        if current > best {
            best = current
        }
    }

    return best, true
}
```