What is the sliding-window technique?

Question

Accepted Answer

The **sliding-window** technique maintains a contiguous range (window) over an array or string and slides it instead of recomputing from scratch, solving many subarray/substring problems in **O(n)**.

## The idea

Expand the window by moving the right edge; shrink it by moving the left edge when a constraint is violated. Reuse the previous computation instead of rescanning.

## Example: max sum of any window of size k

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # sum of first window
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # add new, drop old
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## Complexity

- **Time:** O(n) — each element enters and leaves the window once.
- **Space:** O(1) for fixed windows, O(k) when tracking contents.

## When to use / pitfalls

Use for "longest/shortest/max subarray with property X" problems. For **variable** windows, advance the left pointer to restore the constraint. Watch off-by-one errors when adding/removing boundary elements.

## Why it matters

Sliding window eliminates redundant work, turning O(n·k) recomputation into one pass.

It is the go-to pattern for substring and subarray problems that appear constantly in interviews.

The insight — reuse the previous result instead of recomputing — generalizes to streaming and real-time data.