sliding window
The sliding window is a technique for questions about a contiguous run of elements — a subarray or substring — where you maintain a "window" over part of the data and slide it along instead of re-examining everything from scratch each time. Picture a window frame laid over a row of numbers: as the frame moves one step to the right, one new element enters on the right and (often) one old element leaves on the left. The point is that you update your running answer by accounting only for what entered and what left, never by re-scanning the whole window.
That incremental update is the whole win. The brute-force way to find, say, the maximum sum of any k consecutive elements would recompute each window's sum from scratch, doing O(n·k) — or O(n^2) — work. The sliding window instead computes the first window's sum once, then for each step adds the incoming element and subtracts the outgoing one: each move is O(1), so the entire pass is O(n). Same answer, dramatically less work, with only O(1) extra space.
Windows come in two flavours. A fixed-size window keeps a constant width k and is the simplest case (the running-sum example above). A variable-size window grows and shrinks: you push the right edge out to include more, and pull the left edge in whenever the window violates a condition — the standard pattern for problems like "the longest substring with no repeated character" or "the smallest subarray whose sum is at least S". The art is choosing exactly when to shrink. Sliding window applies only to contiguous segments; for problems where order doesn't matter or elements can be skipped, it isn't the right tool.
int maxSum(const vector<int>& a, int k) {
int sum = 0;
for (int i = 0; i < k; ++i) sum += a[i]; // first window
int best = sum;
for (int i = k; i < a.size(); ++i) {
sum += a[i] - a[i - k]; // slide: add new, drop old
best = max(best, sum);
}
return best; // O(n) time, O(1) space
}Add the entering element, subtract the leaving one — O(n) instead of O(n·k).
Sliding window is really a specialised two-pointer pattern: a left pointer and a right pointer bracket the window, and the elements between them are the window's contents. It needs the answer for a window to be cheaply updatable from the previous window — that incremental update is what makes it O(n).