Skip to content
Back to AlgorithmsAll lessons

Algorithms

Sliding Window

O(n) time — each item enters the window once and leaves it once · O(1) space.

The idea, in plain English

The sliding window technique is like looking through a train window that shows only a fixed number of seats at a time. As the train moves, you do not re-count everyone in view from scratch. You just drop the person who left the view and add the person who entered it.

How it works

  1. 1Add up the first 'window' of k items. That total is your starting sum.
  2. 2Slide the window forward one step: subtract the item that just left, and add the item that just entered.
  3. 3Keep track of the best sum, such as the largest, as the window slides across the whole list.

When you'd use it

Use it for problems about a fixed-size or growing window of items in a row, such as a maximum or minimum sum, the longest run, or an average over a moving range. It is much faster than recomputing each window from scratch.

Common beginner mistakes

  • Recomputing the whole window's sum from scratch each time it slides. That is O(n·k) time and defeats the purpose.
  • Getting the window's start or end position off by one, especially near the end of the list.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Numbers: 2 1 5 1 3 2
Max sum of 3 consecutive: 9

See it in motion

Watch it slideSliding window (k=3)O(n) time — each item enters the window once and leaves it once · O(1) space.

First window covers the first 3 cells — add them up to start: 17.

17
Window sum
17
Best sum
[0, 2]
Window
0/6
Step
Current windowBest windowAnswerOutside window

Not sure this is the right topic? See the learning paths → or where this leads →