The sliding-window technique maintains a contiguous range over a sequence, expanding and shrinking it as you scan — turning many O(n²) substring/subarray problems into O(n). The dual of the two-pointer technique for window-shaped subproblems.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n) |
Θ(n) |
O(n) |
O(1) |
Maintain left and right indices delimiting the current window. Expand right while the window stays valid; when it becomes invalid, shrink from the left until it's valid again. Track the answer as you go. Each index moves forward at most n times — total O(n).
def longest_substring_no_repeat(s):
"""Length of the longest substring with no repeating characters."""
seen = {}
left = best = 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1
seen[ch] = right
best = max(best, right - left + 1)
return best
def min_subarray_sum(arr, target):
"""Smallest contiguous subarray with sum >= target (positive ints)."""
left = 0
s = 0
best = float("inf")
for right, x in enumerate(arr):
s += x
while s >= target:
best = min(best, right - left + 1)
s -= arr[left]
left += 1
return best if best != float("inf") else 0
print(longest_substring_no_repeat("abcabcbb")) # 3 ('abc')
print(min_subarray_sum([2, 3, 1, 2, 4, 3], 7)) # 2 ([4, 3])The trace runs min_subarray_sum([2, 3, 1, 2, 4, 3], 7). The right pointer adds one element per iteration. As soon as the running sum reaches the target, the window is valid, so its length is recorded and the left pointer advances to try a shorter window. The left pointer never moves backwards, and each element is added once and removed at most once, so the total number of pointer moves is at most 2n even though there is a nested while loop. That amortised argument is the key to every sliding-window solution.
A useful template for the variable window is: for each right, include arr[right] in the state; then while the window violates the constraint (or, for "shortest" problems, while it still satisfies it), update the answer if appropriate and remove arr[left] from the state, incrementing left. Whether the answer is recorded inside or after the inner loop depends on whether you want the longest valid window or the shortest one. Getting that placement right is most of the work in a new problem.
There are two families. A fixed-size window of length k slides one position at a time: add the new right element, subtract the element that just fell out on the left, and the aggregate (sum, count, frequency map) is updated in O(1). Moving averages, maximum sum of k consecutive elements and counting anagram occurrences are classic examples. A variable-size window expands the right edge until a constraint is violated, then contracts the left edge until it is satisfied again; it answers "longest" or "shortest" questions such as the longest substring without repeats or the smallest window containing all required characters.
from collections import deque
def max_sum_k(arr, k):
"""Fixed window: maximum sum of any k consecutive elements."""
s = sum(arr[:k])
best = s
for i in range(k, len(arr)):
s += arr[i] - arr[i - k]
best = max(best, s)
return best
def window_max(arr, k):
"""Maximum of every window of size k using a monotonic deque."""
dq, out = deque(), [] # dq holds indices, values decreasing
for i, x in enumerate(arr):
while dq and arr[dq[-1]] <= x:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
out.append(arr[dq[0]])
return out
print(max_sum_k([1, 4, 2, 10, 2, 3, 1, 0, 20], 4)) # 24
print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)) # [3, 3, 5, 5, 6, 7]The sliding-window maximum shows that the window aggregate does not have to be a simple sum. A monotonic deque keeps candidate indices in decreasing value order, so the front is always the current maximum, and each index is pushed and popped once, keeping the whole pass O(n).
Look for three signals: the problem asks about a contiguous subarray or substring; there is an aggregate that can be updated incrementally when one element enters or leaves; and validity is monotonic, meaning that if a window is invalid, growing it further cannot make it valid again (or shrinking it cannot make it invalid). When those hold, sliding window replaces an O(n²) or O(n³) enumeration of all ranges with a single pass.
| Technique | Best for | Typical cost |
|---|---|---|
| Sliding window | contiguous ranges with incremental aggregate | O(n) time, O(1) to O(k) space |
| Two pointers (opposite ends) | pairs in a sorted array | O(n) after sorting |
| Prefix sums + hash map | subarray sums with negative numbers | O(n) time, O(n) space |
| Brute force over all ranges | tiny inputs, verification | O(n²) or worse |
[left, right] inclusive is right - left + 1.seen[ch] >= left; an older occurrence outside the window must not move left backwards.k > len(arr).