Sliding Window

What it is

Sliding window processes contiguous ranges of an array or string while reusing information from neighboring ranges. Instead of recomputing a sum, count, or other property for every candidate, maintain a window and update its state when elements enter or leave.

For a fixed window of length k, consecutive windows share k - 1 elements. Subtracting the outgoing contribution and adding the incoming contribution turns repeated scanning from O(nk) into O(n).

For variable-length windows, two boundaries move forward. Even with a nested shrinking loop, each element usually enters and leaves at most once, giving linear total work when state updates are constant-time.

The key is not simply having two pointers. A useful sliding window needs efficient updates and, for variable-length searches, a reason that moving a boundary cannot discard a better answer.

How to recognize it

Look for these signals:

• The answer concerns a contiguous substring, subarray, or interval.
• Every candidate has a fixed length, or the goal is the longest or shortest valid interval.
• Validity depends on an incrementally maintainable property: sum, distinct count, frequencies, required occurrences, or extrema.
• Extending a window makes an upper-bound constraint harder to satisfy; removing elements makes it easier.
• Alternatively, extending helps satisfy minimum requirements, and shrinking searches for the smallest sufficient window.
• The statement asks for all valid fixed-length starts, or the earliest interval among equally good answers.

Contiguity alone is insufficient. For example, with negative numbers, a sum can increase or decrease when either boundary moves. The usual shrinking-window rule for a sum budget then loses its justification; prefix sums or another technique may be needed.

The core technique

1. Fixed-length windows: update, then evaluate

Use this variant when every candidate contains exactly k elements. Build the first window, then advance both boundaries together.

This template returns the earliest start with the minimum sum:

def minimum_sum_start(a, k):
    if not 1 <= k <= len(a):
        raise ValueError("invalid window length")
    total = sum(a[:k])
    best_sum, best_start = total, 0

    for right in range(k, len(a)):
        total += a[right] - a[right - k]
        if total < best_sum:
            best_sum = total
            best_start = right - k + 1
    return best_start

The strict comparison preserves the earliest start on ties. Fixed-window sums work even when values are negative because no monotonicity argument is required.

The maintained quantity can also describe relationships between neighboring elements. To count unequal adjacent pairs in a length-k window, maintain the k - 1 internal edges. Each shift removes the old leftmost edge and adds the new rightmost edge. For k = 1, the count is always zero. Record starts whose count satisfies the limit.

2. Longest valid windows: expand, then repair

Use this variant when removing elements preserves validity. Add the next element, then move left until the window becomes valid again. The resulting window is the longest valid one ending at the current right boundary.

For nonnegative values and a nonnegative budget:

def longest_within_budget(a, budget):
    left = total = 0
    best_start = best_len = 0

    for right, value in enumerate(a):
        total += value
        while total > budget:
            total -= a[left]
            left += 1

        length = right - left + 1
        if length > best_len:
            best_start, best_len = left, length
    return best_start, best_len

Nonnegativity is essential: extending cannot lower the sum, and removing from the left cannot raise it. Zero-valued elements do not break this reasoning.

Frequency constraints use the same structure. For a bound on distinct values, maintain frequencies and a count of positive-frequency keys. For a bound on equal-value index pairs, adding a value currently occurring f times creates f new pairs. When removing a value occurring f times, subtract f - 1 pairs before decrementing its frequency. These pair counts only increase on expansion and decrease on removal.

For a window without repeated elements, last-seen indices allow a direct jump instead of repeated removal:

def longest_unique(a):
    last_seen = {}
    left = best_start = best_len = 0

    for right, value in enumerate(a):
        left = max(left, last_seen.get(value, -1) + 1)
        last_seen[value] = right
        length = right - left + 1
        if length > best_len:
            best_start, best_len = left, length
    return best_start, best_len

The max prevents an occurrence outside the current window from moving left backward.

3. Shortest sufficient windows: expand until covered, then shrink

Use this variant when the window must contain minimum occurrence quotas. Expansion helps satisfy requirements; removal may break them.

Maintain a frequency map and an unmet count of required value types whose quotas are not satisfied. When adding a value makes its frequency reach its quota, decrement unmet.

Whenever unmet == 0, repeatedly:

1. Evaluate the current window as a shortest-answer candidate.
2. Remove its leftmost value.
3. If that removal takes a required frequency below its quota, increment unmet.
4. Advance left.

Record the candidate before removal: removal may invalidate it. Values with no quota affect length but not demand. An empty set of requirements needs an explicit convention, commonly returning an empty interval.

4. Bounded range: maintain extrema with monotonic deques

Use this variant when validity depends on maximum - minimum staying within a limit. A sum or frequency map cannot efficiently recover an extreme after its current occurrence leaves.

Maintain two deques of indices:

• A maximum deque with values decreasing from front to back.
• A minimum deque with values increasing from front to back.

On insertion, remove dominated indices from each back, then append the new index. Their fronts identify the current maximum and minimum. While their difference exceeds the limit, advance left and remove front indices that fall outside the window.

An older maximum candidate no larger than the new value is unnecessary: the newer value is at least as large and expires later. This dominance argument explains why discarding candidates is safe.

Common mistakes

• Using the wrong shrinking condition. Longest upper-bound windows shrink while invalid; shortest coverage windows shrink while valid.
• Assuming monotonicity. Negative values invalidate the standard sum-budget template.
• Shrinking only once. One removal may not restore validity; use while.
• Updating state in the wrong order. Pair counts and quota transitions depend on frequencies before or after a change.
• Keeping expired extrema. Store indices in deques and remove those before left.
• Mishandling ties. For earliest answers, replace the best only on a strict improvement when processing in increasing boundary order.
• Ignoring empty windows. If no nonempty interval is valid, return the documented empty-result representation.

Complexity

Fixed-length rolling sums and counts take O(n) time and O(1) auxiliary space, excluding collected results.

Variable-length windows take O(n) time when each insertion and removal costs O(1): each boundary advances at most n times. Hash-map operations give expected linear time and O(d) space for tracked distinct values.

Monotonic deques also take O(n) total time because every index is inserted once and removed at most once per deque. Their worst-case space is O(w), where w is the largest active window.

Sliding window does not automatically imply linear time. If maintaining the chosen statistic requires O(log w) updates, total time is typically O(n log w).