vizlearn
Home / Algorithms

Sliding Window

Algorithms & Data StructuresBy Updated

Recomputing a window from scratch is wasteful — it only changed at the edges. Add what enters, subtract what leaves, and an O(n·k) scan becomes O(n).

Controls

window size k3

The Window

step 0
window
–
current
0
best
–

Insight

When a window slides by one, only two elements change. Update the running value instead of recomputing it and each step becomes O(1).

operations0
naive cost0

Complexity

Sliding window O(n)
Naive recompute O(n·k)
Space O(1) / O(k)

Overview

The sliding window technique maintains a contiguous range over an array or string and moves it along, updating a running summary incrementally rather than rebuilding it. It turns O(n·k) into O(n).

The problem it solves

There are two variants: fixed-size and variable-size. A fixed-size window slides one position at a time.

Fixed Windows: Add One, Remove One

To find the maximum sum of k consecutive elements, the naive approach sums each window from scratch. That takes k additions per position, or O(n · k) work in total.

But sliding from position i to i+1 only removes one element and adds one:

Two steps instead of k, no matter how large k is. Compare the step counters as you raise k. The sliding window's count does not move.

For [2, 1, 5, 1, 3] with a window of three, the first sum is 2 + 1 + 5 = 8. Slide one place: subtract 2 and add 1 to get 7. Slide again: subtract 1 and add 3 to get 9. The maximum window sum is 9; each move takes constant work, so the full scan is O(n).

Variable Windows: Grow and Shrink

Harder problems let the window change size. The pattern is always the same:

  • Expand the right edge until the window meets (or violates) some condition.
  • Contract the left edge while the condition still holds, recording the best answer.

Both pointers only ever move forward, so though the code holds nested loops, each element is added once and removed once. Total work is still O(n). That amortised argument is the part people find surprising.

How to Spot One

Reach for a sliding window when the problem asks about a contiguous subarray or substring, and phrases it as longest/shortest/maximum/minimum meeting a condition.

The critical requirement is that the running summary can be updated incrementally. Sums and counts work. If the condition needs the whole window recomputed. A median, say. You need a heavier structure such as a heap or balanced tree alongside the window.

Try it yourself: Sliding Window

  1. Run max-sum with k = 3. Watch each slide subtract one value and add one. Two steps, never three.
  2. Raise k to 5. The naive cost climbs while the sliding-window step count stays flat. That is the whole point.

Where it is used

  • Rate limiting. Requests in the last 60 seconds is a sliding window over timestamps.
  • Streaming statistics. Moving averages, rolling maxima, and any windowed aggregate over a data stream.
  • Network protocols. TCP's sliding window controls how much unacknowledged data may be in flight.
  • Time-series features. Rolling means and standard deviations for forecasting models.
  • Text handling. Finding substrings with given character properties; n-gram extraction.
  • Anomaly detection. Comparing a recent window against a baseline.

Rate limiting is a common production use. A sliding log or counter can enforce a quota over a rolling interval. A fixed-window counter is simpler, but can allow nearly twice the intended rate when requests fall on opposite sides of a window boundary.

Common mistakes with Sliding Window

  • Shrinking in the wrong condition — the longest/shortest inversion described above.
  • Recording the answer at the wrong point, before rather than after restoring validity.
  • Not removing from the state when shrinking, so counts drift.
  • Using it on non-contiguous problems. Sliding window is only for runs; subsequences need dynamic programming.
  • Recomputing the aggregate from scratch, which discards the entire edge.
  • Off-by-one in the window size: the width is right - left + 1.

Sources and next steps

Run it in Python

A fixed window and a variable one. The first shows the recomputation the technique removes; the second grows and shrinks on demand, which is where most of the real problems live.

sliding_window.pyPython 3
Output
How the code works
  1. total += a[i] - a[i - k]The whole technique in one line: add what just entered, subtract what just left. The window's value is carried forward rather than rebuilt, turning O(n·k) into O(n).
  2. total = sum(a[:k])The first window still has to be computed the slow way. Every sliding window has this setup step, and it is a common place to get the bounds wrong by one.
  3. if ch in seen and seen[ch] >= start:The second condition is the subtle one. A repeat only matters if it is inside the current window; an older occurrence already fell off the left edge and must be ignored.
  4. start = seen[ch] + 1The left edge jumps straight past the previous occurrence instead of creeping forward one at a time. Both are correct; this one keeps the whole scan linear.
  5. i - start + 1The window length, and the reason the dictionary stores indices rather than counts. Storing counts works too, but then the left edge has to walk, and the code gets longer.
Change one thing
  • Raise k to 6 and compare the two operation counts again. The gap grows with the window, because the naive version pays for it every step.
  • Run longest_unique on "abba". The second a is what the seen[ch] >= start guard is protecting against — drop it and the answer is wrong.
  • Adapt the fixed window to a running average. Same two lines, and it is how a moving average over a data stream is actually computed.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: set target to its maximum (30). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. The fixed-size window updates its sum with one line. Which?
  2. In the longest-unique-substring window, why is the check 'ch in seen and seen[ch] >= start' rather than just 'ch in seen'?
  3. Storing the last index of each character rather than a count lets the left edge:





 Cheat sheet
Sliding Window
Slide a fixed or variable-size window across an array, updating a running total to replace an O(n*k) nested loop with O(n).
ALGORITHMS · vizlearn.in/dsa/sliding_window.html
More in Algorithms
AlgorithmsGreedy AlgorithmsAlgorithmsBacktracking Search MethodAlgorithmsDynamic ProgrammingAlgorithmsKMP String Matching
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact