Overview
The Sliding Window technique tackles problems about contiguous subarrays or substrings by maintaining a 'window' that slides across the data. Rather than recomputing a result for every window from scratch, it reuses the previous window's work and only accounts for the elements that enter and leave.
For a fixed-size window of length k — for example, finding the maximum-sum subarray of size k — this reuse turns a naïve O(n·k) approach into a single O(n) pass. Keeping a running window sum, adding the entering element and subtracting the leaving one, is the core insight.
How Sliding Window works
- Sum the first k elements to initialise the window sum, and record it as the current best.
- Slide the window one position to the right by adding the new element that enters on the right.
- Subtract the element that just left the window on the left, so the sum stays in sync in O(1).
- Compare the updated window sum against the best seen so far and update it when larger.
- Repeat until the window reaches the end of the array; the recorded best is the answer.
When to use it
- Maximum or minimum sum subarray of a fixed size k — a classic warm-up interview problem.
- Computing moving averages over a stream of readings, such as sensor or price data.
- Variable-size window variants: longest substring without repeating characters, or the smallest subarray whose sum exceeds a target.
- Any contiguous-range query where neighbouring windows overlap heavily and the answer can be updated incrementally.
Complexity analysis
Each element enters the window once and leaves once, and every slide is an O(1) add-and-subtract, so the whole scan is O(n) time and O(1) space. This beats the naïve method that re-sums each of the n−k+1 windows independently in O(k), which totals O(n·k).
Frequently asked questions
How does the running sum avoid recomputation?
Two consecutive windows share all but two elements. Instead of adding up all k values again, you add the one element that just entered and subtract the one that just left — an O(1) update — so the sum is always current without rescanning.
What is the difference between fixed-size and variable-size windows?
A fixed-size window always spans exactly k elements, so it slides by moving both edges together. A variable-size window grows its right edge to satisfy a condition and shrinks its left edge to stay valid, which suits problems like the smallest subarray with a given sum.
Does Sliding Window work with negative numbers?
For a fixed-size window the running sum works with any values, negative included, because it simply tracks the exact sum. Variable-size windows that rely on shrinking when a sum grows too large, however, assume non-negative values; with negatives you typically switch to a prefix-sum or other approach.