Sliding Window

Also Known As

TL;DR

Explanation

Instead of recomputing a result from scratch for each position (O(n²) or worse), the sliding window maintains running state — adding the new element entering the window and removing the one leaving. Fixed-size windows compute moving averages or max sums. Variable-size windows find the shortest/longest subarray meeting a constraint. Common uses: maximum sum subarray, longest substring without repeating characters, minimum window substring.

Diagram

flowchart LR
    ARR[Array: 1 3 5 2 4 6 1<br/>Find max sum of 3 elements]
    subgraph Naive_O_n_k
        N1[Check 1,3,5 = 9]
        N2[Check 3,5,2 = 10]
        N3[Check 5,2,4 = 11]
        N1 --> N2 --> N3
    end
    subgraph SlidingWindow_O_n
        W1[Window 1,3,5 = 9]
        W2[Slide: remove 1 add 2<br/>9-1+2 = 10]
        W3[Slide: remove 3 add 4<br/>10-3+4 = 11]
        W1 --> W2 --> W3
    end
    RESULT[Max sum = 11]
style W1 fill:#1f6feb,color:#fff
style W3 fill:#238636,color:#fff
style RESULT fill:#238636,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Not expanding/shrinking the window based on the constraint — moving a fixed step instead.
• Forgetting to update the running state when removing the leftmost element.
• Using a fixed-size window when a variable-size window is needed (or vice versa).
• Off-by-one errors in window boundary calculations.

Code Examples

// O(n²) — recompute sum from scratch for each window:
function maxSumSubarray(array $arr, int $k): int {
    $max = 0;
    for ($i = 0; $i <= count($arr) - $k; $i++) {
        $sum = array_sum(array_slice($arr, $i, $k)); // O(k) per position
        $max = max($max, $sum);
    }
    return $max;
}

// O(n) — maintain running window sum:
function maxSumSubarray(array $arr, int $k): int {
    $windowSum = array_sum(array_slice($arr, 0, $k));
    $max = $windowSum;
    for ($i = $k; $i < count($arr); $i++) {
        $windowSum += $arr[$i] - $arr[$i - $k]; // Slide: add new, remove old
        $max = max($max, $windowSum);
    }
    return $max;
}

References

• ↗ https://en.wikipedia.org/wiki/Sliding_window_protocol

Tags

Related Terms