Two pointers and the sliding window turn many array and string problems from $O(n^2)$ into $O(n)$ by moving one or two indices across the data instead of re-scanning overlapping ranges. They are less a single algorithm than a way of seeing structure that lets you avoid redundant work.
Two pointers
On sorted data, start one index at each end and move them inward based on a comparison. For the pair-sum problem, if the current pair sums too low you can only help by raising the small end, and if too high you must lower the large end, so each move is forced and correct. This monotonic reasoning is what collapses an $O(n^2)$ search over pairs into a single $O(n)$ sweep.
Sliding window
A window is a contiguous range tracked by its two ends and a running summary of what it contains (a sum, a count, a last-seen map). You expand the right end to include new elements and shrink the left end while the window violates its constraint, recording the best window seen. The why behind its linear cost is an amortization argument: each index enters the window once and leaves at most once, so the total number of pointer moves is at most $2n$ regardless of how the window grows and shrinks.
Recognizing the pattern
Reach for two pointers on sorted arrays and for pair, triplet, partition, or merge problems. Reach for a sliding window when the question asks for the longest, shortest, or count of a contiguous subarray or substring meeting a condition. Windows come in two flavors: fixed size (slide a constant-width window) and variable size (grow and shrink to satisfy a constraint), and recognizing which you need is half the work.
Step by step
- Two pointers: start one index at each end and move them based on the comparison.
- Sliding window: expand the right edge to include new elements.
- Update the running summary (a count, sum, or last-seen map).
- Shrink from the left while the window violates the condition, recording the best.
def two_sum_sorted(a, target):
i, j = 0, len(a) - 1
while i < j:
s = a[i] + a[j]
if s == target:
return (i, j)
if s < target: # too small: only raising the low end can help
i += 1
else: # too large: only lowering the high end can help
j -= 1
return None
def longest_unique_substring(s):
seen, start, best = {}, 0, 0
for i, ch in enumerate(s):
if ch in seen and seen[ch] >= start:
start = seen[ch] + 1 # jump the left edge past the earlier copy
seen[ch] = i
best = max(best, i - start + 1)
return best
Complexity (time and space)
Both are $O(n)$ time. Two pointers is $O(1)$ space; the sliding window is $O(k)$ for whatever it tracks about the window, here the set of characters currently inside it. The linear time holds even though the window expands and contracts, because of the amortized at-most-$2n$ pointer moves.
Worked example
The two-pointer search finds the pair summing to 15, and the window finds the longest repeat-free substring of "abcabcbb":
print(two_sum_sorted([1, 2, 4, 7, 11], 15)) # (2, 4) -> 4 + 11
print(longest_unique_substring("abcabcbb")) # 3 -> "abc"
Follow-up questions
- Why is the sliding window O(n) despite shrinking and growing? Each index enters and leaves the window at most once, so total pointer movement is bounded by $2n$ (an amortized argument).
- When do two pointers require sorted input? Whenever correctness depends on the monotonic argument that one move is always the right one, as in pair-sum.
- Fixed vs variable window? Fixed slides a constant width; variable grows and shrinks to satisfy a constraint, used for longest/shortest problems.
- Why is moving the larger end safe in two-sum? If the sum is too large, no choice of a larger low element can fix it, so the high end must decrease; the symmetric argument covers too-small sums.
- What summary does the window keep? Whatever the constraint needs: a running sum, a frequency count, or a last-seen index map.
References
- Skiena, The Algorithm Design Manual (3rd ed.).
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (CLRS, 4th ed.).
- Sedgewick & Wayne, Algorithms (4th ed.).