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

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.

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.

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.

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

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.

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:

O(n)

Space complexity depends on the state:

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:

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.