How sliding window works
A window is a run of neighbouring elements, a[left..right]. Many array problems ask about such runs: the largest sum of 7 days in a row, the longest stretch without a repeated character. A nested loop checks every run, n(n + 1)/2 of them. A sliding window moves along the array instead, adding the element that enters on the right and subtracting the one that leaves on the left, so the window's sum stays up to date in O(1) per move.
The problem animated here: find the length of the shortest run of neighbouring numbers whose sum is at least a target (LeetCode 209). All numbers are positive.
Picture a caterpillar crawling along the array (Codility calls this the caterpillar method). Its head, right, stretches forward one value at a time until the body holds enough. Then its tail, left, pulls in for as long as the body still holds enough, and every time it does, the caterpillar is a little shorter. Neither end ever moves backwards.
Positive numbers are what make this safe. Adding a value can only raise the total and removing one can only lower it. So once a window reaches the target, no longer window starting at the same left end can be shorter, and the left end can move on for good. With zeros or negatives that argument breaks.
Windows come in two kinds. A fixed-size window of k elements adds a[right] and subtracts a[right − k] at every step. A variable window, like this one, grows until a condition holds and shrinks while it still holds.
The algorithm in 5 steps
- 1 Set
best = 0(meaning "none yet"),left = 0andtotal = 0. - 2 For each
rightfrom 0 to n − 1, adda[right]tototal. - 3 While
total >= target, the window works: if it is shorter thanbest, record its lengthright − left + 1. - 4 Still inside that loop, subtract
a[left]and moveleftone step right. - 5 Return
best. 0 means no run reaches the target.
Worked example
This is the first example from LeetCode 209, run by the same code as the visualizer. The table lists every value added, every new best and every value removed; the checks in between are counted but not listed.
Input: [2, 3, 1, 2, 4, 3], sum to reach7
- Step 2 Add a[0] = 2 on the right: total = 2. The window is index 0. 231243
- Step 4 Add a[1] = 3 on the right: total = 5. The window is indices 0–1. 231243
- Step 6 Add a[2] = 1 on the right: total = 6. The window is indices 0–2. 231243
- Step 8 Add a[3] = 2 on the right: total = 8. The window is indices 0–3. 231243
- Step 10 best = 4. Now try a shorter window: drop values from the left. 231243
- Step 11 Remove a[0] = 2 from the left: total = 6. The window is indices 1–3. 231243
- Step 13 Add a[4] = 4 on the right: total = 10. The window is indices 1–4. 231243
- Step 15 Remove a[1] = 3 from the left: total = 7. The window is indices 2–4. 231243
Show the remaining 7 rows
- Step 17 best = 3. Now try a shorter window: drop values from the left. 231243
- Step 18 Remove a[2] = 1 from the left: total = 6. The window is indices 3–4. 231243
- Step 20 Add a[5] = 3 on the right: total = 9. The window is indices 3–5. 231243
- Step 22 Remove a[3] = 2 from the left: total = 7. The window is indices 4–5. 231243
- Step 24 best = 2. Now try a shorter window: drop values from the left. 231243
- Step 25 Remove a[4] = 4 from the left: total = 3. The window is index 5. 231243
- Step 27 The right edge reached the end. Shortest run: indices 4–5 (4 + 3 = 7). Return 2. 231243
Result: 2, after 6 values added and 5 values removed (28 animation steps), out of 21 possible runs.
Time and space complexity
Best
O(n)The right edge always visits all n values, even if the answer is found early.
Average
O(n)Each value is added once and removed at most once, so the inner while loop runs at most n times in total, not n times per value.
Worst
O(n)At most 2n pointer moves: n additions on the right and n removals on the left.
Space
O(1)Just left, right, the running total and the best length.
- Input:
- Positive numbers
- Pointer moves:
- At most 2n
- Returns:
- Shortest length or 0
- Extra memory:
- None
The visualizer's 10 numbers have 55 runs of neighbouring values, and a nested loop would sum every one. The window added 10 values and removed 6 values: 16 moves, never more than 2n = 20. For 1,000 numbers that is 500,500 runs against at most 2,000 moves.
When to use it, and when not to
Good fit
- Fixed-length runs: the best 7-day total of daily sales, the moving average of the last k readings, or the maximum sum of any k consecutive values.
- Longest or shortest run with a condition: the longest substring without repeating characters, or the shortest subarray reaching a sum, as here.
- Counting with a window: the smallest substring that contains every required character (minimum window substring), using a count of characters inside the window.
- Streams where only recent data matters, such as counting requests in the last 60 seconds for a rate limiter.
Pick something else when
- The numbers can be zero or negative and the condition is a sum. Shrinking may then throw away a window that a later negative value would have fixed. Use prefix sums with a hash map for "sum exactly k" (LeetCode 560), or prefix sums with a monotonic deque for "sum at least k" (LeetCode 862).
- The elements do not have to be neighbours. Subsequence problems, such as the longest increasing subsequence, need dynamic programming.
- The condition is not monotonic: making the window bigger does not reliably move you towards or away from it.
Common mistakes and bugs
-
1.if instead of while when shrinking
One removal per step is not enough. On
[1, 1, 1, 10]with target 10, the window first works at length 4; withifit drops one value and the loop ends, returning 4. Withwhileit keeps shrinking down to[10]and returns the right answer, 1. -
2.Off-by-one window length
The window
a[left..right]holdsright − left + 1values, notright − left. Record the length before you moveleft, or the count is one short. -
3.Using it with negative numbers
On
[-1, 2]with target 2 the total goes −1, then 1, never reaches 2, and the code returns 0. But[2]on its own works: the window could only find it by dropping the −1, and it only drops values once the target is reached. The method is only correct for positive values. -
4.Recomputing the window sum
Adding up
a[left..right]from scratch at every step turns O(n) into O(n · k). The whole point is the running total: add what enters, subtract what leaves. -
5.Confusing "no answer" with length 0
This code uses
best = 0as "none found", which works because a valid run has at least one element. If you start from infinity instead, convert it to 0 (or whatever the problem asks for) before returning.
Interview questions
Try answering before you open the model answer.
Q1 Longest substring without repeating characters.
Model answer: Keep a window s[left..right] with no repeats and a map from each character to its last index. For each right, if s[right] was seen at an index >= left, move left to just past that index. Update the best length right − left + 1. Each index enters and leaves once: O(n) time, O(alphabet) space.
Q2 Maximum sum of any k consecutive elements.
Model answer: Fixed-size window. Sum the first k values, then for each next index i add a[i] and subtract a[i − k], keeping the largest total. That is n − k + 1 windows in O(n) time and O(1) space, against O(n · k) for summing every window separately.
Q3 Why is the shortest-subarray code O(n) when it has a while loop inside a for loop?
Model answer: Count the work by what moves. The for loop moves right n times. Every pass of the inner while loop moves left one step, and left only goes forward and never past n, so across the whole run the inner loop executes at most n times in total. Together that is at most 2n steps, which is O(n). This style of counting is called amortized analysis.
Q4 Minimum window substring: the shortest part of s containing every character of t.
Model answer: Count the characters t needs. Grow the window on the right and track how many required characters are fully covered. When all are covered, shrink from the left while they stay covered, recording the shortest window, then grow again. O(|s| + |t|) time with a fixed-size count array.
Q5 Sliding window maximum: the maximum of every window of size k.
Model answer: Keep a deque of indices whose values are in decreasing order. For each i, pop from the back while the value there is <= a[i], push i, and pop from the front if that index has left the window. The front is the window's maximum. Each index is pushed and popped once: O(n).
Frequently asked questions
What is the sliding window technique?
A way to solve problems about runs of neighbouring elements in O(n). Two indices mark the left and right ends of a window. Moving right adds an element and moving left removes one, and a running value, such as the window's sum, is updated in O(1) per move instead of being recomputed for every possible run.
What is the difference between a fixed and a variable sliding window?
A fixed window always holds k elements, so both ends move together: add a[right], subtract a[right − k]. A variable window grows on the right until a condition holds, then shrinks from the left while it still holds, so its length changes as it goes. This page animates a variable window.
Why does this sliding window need positive numbers?
Because the shrinking step assumes that removing a value lowers the total and adding one raises it. With only positive values, once a window reaches the target, no longer window from the same left end can be shorter, so moving left forward is safe. Zeros and negatives break that guarantee; prefix sums are the usual fix.
What is the time complexity of the sliding window technique?
O(n). Each element enters the window once on the right and leaves at most once on the left, so the two pointers make at most 2n moves in total, even though the code has a loop inside a loop. Extra space is O(1) for sums, or the size of the character set when the window keeps counts.
Is a sliding window the same as two pointers?
It is a kind of two-pointer technique. In a sliding window both pointers move in the same direction and everything between them matters. In the classic pair-sum version of two pointers, they start at opposite ends and only the two values they point at matter.