Sliding Window
Keep a running answer for a contiguous range, adding the item that enters and removing the one that leaves, instead of recomputing every window.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
A train window: as the train moves, one new tree appears on the right and one old tree disappears on the left. You don’t need to look at the whole view again.
Fixed window (size k)
Compute the first window’s sum once. Then for each step: sum += a[r] − a[r − k]. That is O(n) instead of O(n·k).
Variable window
Two pointers l and r mark the window. Move r to grow it. Whenever the window breaks a rule (a repeated letter, a sum too big), move l to shrink it until it is valid again. Each index enters once and leaves once, so the total is O(n), even with the inner while.
Built on arrays (Ch1) and two pointers. Not on the exam.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Each slide adds one number and subtracts one. Try k = 1 and k = n to see the edges.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int maxSum(const vector<int>& a, int k) { // fixed-size window
int sum = 0;
for (int i = 0; i < k; i++) sum += a[i];
int best = sum;
for (int r = k; r < (int)a.size(); r++) {
sum += a[r] - a[r - k]; // add new, drop old
best = max(best, sum);
}
return best;
}
int longestUnique(const string& s) { // variable-size window
int seen[256] = {};
int best = 0;
for (int l = 0, r = 0; r < (int)s.size(); r++) {
seen[(unsigned char)s[r]]++;
while (seen[(unsigned char)s[r]] > 1) seen[(unsigned char)s[l++]]--; // shrink until valid
best = max(best, r - l + 1);
}
return best;
}
int main() {
cout << "max sum of 3: " << maxSum({2, 1, 5, 1, 3, 2, 7, 1}, 3) << "\n";
cout << "longest without repeats in \"abcabcbb\": " << longestUnique("abcabcbb") << "\n";
}max sum of 3: 12 longest without repeats in "abcabcbb": 3
05Complexity
| recompute every window | O(n·k) |
|---|---|
| fixed sliding window | O(n) |
| variable window (grow/shrink) | O(n): each item enters and leaves once |
| Extra space | O(1), or O(alphabet) for a frequency table |
Sliding windows work on contiguous ranges (subarrays, substrings), not subsequences.
06Watch
Sliding Window in 7 minutes
Why this one: Fixed vs variable windows in 7 minutes.
Sliding Window: Best Time to Buy and Sell Stock
Why this one: NeetCode applies the window idea to Best Time to Buy and Sell Stock.
Original class slides (Python, by the course's lecture authors):Sliding Window
07Exam lens
Likely questions
- What is the difference between a fixed and a variable sliding window?
- Why is the variable window still O(n) even though it has a nested while loop?
Common mistakes
- Off-by-one when dropping the old item. It is
a[r − k], nota[r − k + 1]. - Using a window on a problem that asks for a subsequence (not contiguous).
- Forgetting to update the answer after shrinking.
08Quick check
09Practice
🟢 Trace by hand
Max sum of k = 3 in 2 1 5 1 3 2 7 1. List each window sum.
Show answer
8, 7, 9, 6, 12, 10 → best 12 (3 2 7).
🟡 Implement it
Find the length of the shortest subarray with sum ≥ S (all numbers positive).
Hint
Grow r, adding to sum. While sum >= S, record r − l + 1 and shrink from the left.
🔴 Solve problems
Hint
Track the lowest price so far; the window is "buy day … today".
Hint
This page's
longestUnique().Hint
Variable window. Shrink while the sum is big enough.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.