# 2.5 Sliding Windows

Sliding windows maintain a contiguous subarray `[l, r)` while both endpoints move forward. The window expands to include new elements and contracts to restore a constraint. When both pointers are monotone, each index is visited a constant number of times, giving linear time.

This technique applies when a property over a range can be updated incrementally as elements enter or leave the window.

## Problem

Given an array or string, find a contiguous range that satisfies a condition such as:

* sum or cost bounded by a limit
* at most `k` distinct elements
* no repeated elements
* frequency constraints on characters

A direct approach tries all ranges and costs `O(n^2)`.

## Model

Maintain indices `l` and `r` with a half-open window `[l, r)`. Keep a state `S` that summarizes the window. Provide two operations:

* `add(x)`: update `S` when including `x = A[r]`
* `remove(x)`: update `S` when excluding `x = A[l]`

The loop expands `r` and contracts `l` to maintain a validity predicate `valid(S)`.

## Template

```go id="1q3m1x"
l := 0
best := 0 // or appropriate identity

for r := 0; r < n; r++ {
	add(A[r])

	for !valid() {
		remove(A[l])
		l++
	}

	// window [l, r] is valid here (or [l, r) depending on convention)
	best = update(best, l, r)
}
```

Invariant:

After the inner loop finishes, the window satisfies `valid(S)`. All indices strictly before `l` are excluded because they would violate `valid(S)` if reintroduced.

## Fixed-Size Window

When the window size is fixed to `k`, only one pointer effectively moves.

Example: maximum sum of any subarray of length `k`.

```go id="9k6r1f"
func MaxSumFixed(a []int, k int) int {
	if k == 0 || len(a) < k {
		return 0
	}

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

	best := sum

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

	return best
}
```

Invariant:

At step `r`, `sum` equals the sum of the window `[r-k+1, r]`.

## Variable-Size Window with Sum Constraint

Example: longest subarray with sum at most `K` when all values are nonnegative.

```go id="r4t0yq"
func LongestAtMostK(a []int, K int) int {
	l := 0
	sum := 0
	best := 0

	for r := 0; r < len(a); r++ {
		sum += a[r]

		for sum > K {
			sum -= a[l]
			l++
		}

		if r-l+1 > best {
			best = r - l + 1
		}
	}

	return best
}
```

Invariant:

After contraction, `sum <= K`, and the window `[l, r]` is the longest valid window ending at `r`.

The nonnegativity condition ensures that increasing `l` decreases `sum`, which makes contraction correct.

## Distinct Elements Constraint

Example: longest substring with all distinct characters.

```go id="9q1h2u"
func LongestUnique(s string) int {
	last := make(map[byte]int) // last index + 1
	l := 0
	best := 0

	for r := 0; r < len(s); r++ {
		if pos, ok := last[s[r]]; ok && pos > l {
			l = pos
		}

		last[s[r]] = r + 1

		if r-l+1 > best {
			best = r - l + 1
		}
	}

	return best
}
```

Invariant:

The window `[l, r]` contains no duplicate characters. The map stores the last seen position, allowing `l` to jump forward in one step.

## At Most K Distinct Elements

```go id="m7h8ga"
func LongestAtMostKDistinct(a []int, K int) int {
	count := make(map[int]int)
	l := 0
	best := 0

	for r := 0; r < len(a); r++ {
		count[a[r]]++

		for len(count) > K {
			count[a[l]]--
			if count[a[l]] == 0 {
				delete(count, a[l])
			}
			l++
		}

		if r-l+1 > best {
			best = r - l + 1
		}
	}

	return best
}
```

Invariant:

The window contains at most `K` distinct values, tracked by the map `count`.

## Minimum Window Cover

Example: smallest substring of `s` that contains all characters of `t`.

```go id="w2f0op"
func MinWindow(s, t string) string {
	need := make(map[byte]int)
	for i := 0; i < len(t); i++ {
		need[t[i]]++
	}

	have := make(map[byte]int)
	required := len(need)
	formed := 0

	l := 0
	bestLen := int(^uint(0) >> 1)
	bestL := 0

	for r := 0; r < len(s); r++ {
		c := s[r]
		have[c]++

		if have[c] == need[c] && need[c] > 0 {
			formed++
		}

		for formed == required {
			if r-l+1 < bestLen {
				bestLen = r - l + 1
				bestL = l
			}

			d := s[l]
			have[d]--
			if have[d] < need[d] && need[d] > 0 {
				formed--
			}
			l++
		}
	}

	if bestLen == int(^uint(0)>>1) {
		return ""
	}
	return s[bestL : bestL+bestLen]
}
```

Invariant:

When `formed == required`, the window covers all required characters. The inner loop contracts to find the minimal such window ending at `r`.

## Complexity

Both pointers move forward at most `n` times.

Time complexity:

```text id="t2v9mb"
O(n)
```

Space complexity depends on the state:

```text id="n2j1k3"
O(1) or O(k)
```

where `k` is the number of distinct elements tracked.

## When It Applies

Sliding windows require that:

* the property can be updated incrementally
* removing elements from the left can restore validity
* pointer movement is monotone

For sum constraints, nonnegative values guarantee monotonicity. With negative values, removing elements may increase the sum, which breaks the method.

## Common Pitfalls

Using sliding windows with arbitrary integers for sum constraints leads to incorrect results. Without monotonicity, contraction does not reliably restore validity.

Mixing inclusive `[l, r]` and half-open `[l, r)` conventions causes off-by-one errors. Choose one and keep it consistent.

Forgetting to update state when removing elements leads to stale counts or sums.

Incorrect loop nesting often appears as:

```go id="3r9d8c"
for r := 0; r < n; r++ {
	for !valid() {
		l++
	}
}
```

without calling `remove`. The state must reflect both additions and removals.

## Design Pattern

A sliding window algorithm has three components:

1. A state that summarizes the current window
2. A validity condition over that state
3. Rules for expanding and contracting the window

Once these are defined, the algorithm follows directly from the template.

## Takeaway

Sliding windows convert quadratic range enumeration into linear scanning by maintaining a valid interval with two monotone pointers. The method succeeds when the constraint can be enforced by local updates and restored by moving the left boundary forward.