The Sliding Window Algorithm
Recomputing a sum over every subarray is quadratic; updating one running total as a window slides is linear. The pattern looks like a nested loop but is not one, and understanding why the inner while does not multiply the cost is the difference between using this technique and merely recognising it.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int longestAtMostK(vector<int>& a, int k) {
int left = 0, sum = 0, best = 0;
for (int right = 0; right < (int)a.size(); right++) {
sum += a[right];
while (sum > k) {
sum -= a[left];
left++;
}
int len = right - left + 1;
if (len > best) best = len;
}
return best;
}
int main() {
vector<int> a = {3, 1, 2, 7, 4, 2, 1, 1, 5};
cout << longestAtMostK(a, 8) << endl;
return 0;
}Finds the longest run of non-negative numbers whose sum stays at or below k, by expanding right and pulling left forward only when the sum overshoots.
How it works, step by step
The window is the range [left, right]
right always advances by one per outer iteration; left only moves when the window becomes invalid. The invariant is that after the while loop, the window is the longest valid one ending at right.
Incremental update replaces recomputation
Adding a[right] and subtracting a[left] keeps sum correct in O(1). The naive version recomputes the sum from scratch for every window, which is what makes it O(n squared). The entire speedup is this one substitution.
The inner while is amortised, not nested
left never decreases and cannot exceed right, so across the whole run the while body executes at most n times total. Some outer iterations run it many times and most run it zero, but the sum over all iterations is bounded by n — that is why the algorithm is O(n) despite looking quadratic.
Shrink until valid, then measure
The order matters: expand, restore the invariant, then record. Measuring before the while loop would count an invalid window; shrinking before adding a[right] would measure a window that is not maximal.
Length is right - left + 1, always
Inclusive bounds on both ends mean the count includes both endpoints. A window where left == right has length 1, not 0 — the +1 is not decoration.
Complexity
Each index is added once by right and removed at most once by left, so the total pointer movement is bounded by 2n; the technique stops being valid the moment shrinking the window can no longer restore validity, which is what negative numbers do to a sum-based window.
Common bugs
Negative numbers silently break the sum window
The shrink loop assumes removing an element makes the sum smaller. With negative values that is false — dropping a -5 increases the sum, so the while loop can shrink the window to nothing and still not be valid, or terminate early and miss the answer. For arrays with negatives, use prefix sums with a map instead.
Using if instead of while when shrinking
One large element can invalidate the window by more than a single removal can fix. if (sum > k) removes exactly one element and moves on, leaving sum still over the limit, and every subsequent window is measured against a corrupt state. Put a large value in the middle of the array, step through in DryRun, and watch sum stay above k after the if has already run.
Updating best before restoring the invariant
Recording right - left + 1 above the while loop counts windows that violate the constraint, so the answer comes back too large. The measurement must be the last thing in the loop body.
Forgetting to subtract when advancing left
Writing left++ without sum -= a[left] leaves the running total describing a window that no longer exists. The result is usually a too-small answer that looks plausible on small inputs. Every pointer move must be paired with the matching state update — that pairing is the whole contract of the technique.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
Why is sliding window O(n) if it has a nested loop?
Because the inner while loop is bounded globally, not per iteration. The left pointer only ever moves forward and can never pass right, so across the entire run it advances at most n times in total. The outer loop contributes n steps and the inner loop contributes at most n more, giving O(n) overall — this is amortised analysis, not worst-case-per-iteration.
When should I use a sliding window?
When the answer is a contiguous subarray or substring, and you can update the window's state in O(1) as elements enter and leave. It also needs a monotonic validity property: if a window is invalid, shrinking it from the left must be able to make it valid again. Sum-with-non-negative-values and character-frequency problems both satisfy this.
What is the difference between fixed and variable sliding windows?
A fixed window has a known size k, so left is always right - k + 1 and you add and remove one element per step with no inner loop. A variable window's size is determined by a constraint, so an inner while loop shrinks it until the constraint holds again. Fixed windows are simpler and strictly O(n) per step.
Why does sliding window fail with negative numbers?
Because the shrink step assumes removing an element reduces the sum. With negatives, removing an element can increase the sum, so the loop has no reliable way to restore validity and the window boundaries stop being meaningful. Prefix sums combined with a hash map handle those cases instead.