Patterns: Two Pointers, Sliding Window, and Friends
This chapter covers the recurring patterns you'll see in algorithm problems: two pointers, sliding window, backtracking, prefix sums, monotonic stacks.
Two Pointers
Two indices into an array (or string), usually moving toward each other or in the same direction. Useful for sorted data and in-place operations.
Pair Sum in a Sorted Array
def pair_sum(arr, target):
lo, hi = 0, len(arr) - 1
while lo < hi:
s = arr[lo] + arr[hi]
if s == target:
return (lo, hi)
if s < target:
lo += 1
else:
hi -= 1
return None
O(n). Works because the array is sorted: if the sum is too small, only moving lo right can increase it; if too big, only moving hi left can decrease it.
Remove Duplicates In-Place
def dedup(arr):
if not arr:
return 0
write = 0
for read in range(len(arr)):
if arr[read] != arr[write]:
write += 1
arr[write] = arr[read]
return write + 1 # length of deduplicated prefix
O(n) time, O(1) space. write and read are the two pointers; both move forward.
Reverse a String
def reverse(arr):
lo, hi = 0, len(arr) - 1
while lo < hi:
arr[lo], arr[hi] = arr[hi], arr[lo]
lo += 1
hi -= 1
Classic pair converging from the ends.
Sliding Window
A "window" (range of indices) slides through the array. Useful when the answer depends on contiguous subarrays.
Fixed-Size Window: Max Sum of K Consecutive Elements
def max_sum_k(arr, k):
if len(arr) < k:
return None
curr = sum(arr[:k])
best = curr
for i in range(k, len(arr)):
curr += arr[i] - arr[i - k] # slide: add new, remove old
best = max(best, curr)
return best
O(n). Instead of re-summing each window (O(nk)), update incrementally.
Variable-Size Window: Longest Substring Without Repeating Characters
def longest_unique(s):
seen = {}
lo = 0
best = 0
for hi, c in enumerate(s):
if c in seen and seen[c] >= lo:
lo = seen[c] + 1
seen[c] = hi
best = max(best, hi - lo + 1)
return best
O(n). The window is [lo, hi]. When a duplicate appears, shrink the left edge past the previous occurrence.
Minimum Window Substring
"Smallest window in s that contains all characters of t."
from collections import Counter
def min_window(s, t):
need = Counter(t)
missing = len(t)
lo, best = 0, (0, float("inf"))
for hi, c in enumerate(s):
if need[c] > 0:
missing -= 1
need[c] -= 1
while missing == 0:
if hi - lo < best[1] - best[0]:
best = (lo, hi)
need[s[lo]] += 1
if need[s[lo]] > 0:
missing += 1
lo += 1
return s[best[0]:best[1] + 1] if best[1] != float("inf") else ""
Grow the window until it satisfies the constraint; shrink it while it still does; track the minimum.
Backtracking
Explore a solution space by making choices, recursing, and undoing choices that don't lead anywhere. Classic pattern for permutations, combinations, board-like puzzles.
Generate All Permutations
def permutations(nums):
result = []
def backtrack(path):
if len(path) == len(nums):
result.append(path[:])
return
for n in nums:
if n not in path:
path.append(n)
backtrack(path)
path.pop() # undo
backtrack([])
return result
The .pop() after the recursive call is the "backtrack". It undoes the choice so we can try another.
N-Queens
Place N queens on an N×N board such that no two attack each other.
def solve_n_queens(n):
result = []
cols = set()
diag1 = set() # r - c
diag2 = set() # r + c
def place(r, board):
if r == n:
result.append(["." * c + "Q" + "." * (n - c - 1) for c in board])
return
for c in range(n):
if c in cols or (r - c) in diag1 or (r + c) in diag2:
continue
cols.add(c); diag1.add(r - c); diag2.add(r + c)
place(r + 1, board + [c])
cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)
place(0, [])
return result
Backtracking with pruning: skip any column that conflicts. The three sets track conflicts in O(1).
Prefix Sums
Precompute running totals so range sums are O(1).
def build_prefix(arr):
prefix = [0] * (len(arr) + 1)
for i, x in enumerate(arr):
prefix[i + 1] = prefix[i] + x
return prefix
def range_sum(prefix, lo, hi):
return prefix[hi + 1] - prefix[lo]
O(n) to build. O(1) per query. Worth it if you make many range queries.
Subarray Sum Equals K
Count subarrays with sum equal to k.
from collections import defaultdict
def subarray_sum(nums, k):
counts = defaultdict(int)
counts[0] = 1
curr = 0
result = 0
for x in nums:
curr += x
result += counts[curr - k]
counts[curr] += 1
return result
Prefix sums plus hash lookup: O(n) total. Brute force is O(n^2).
Monotonic Stack
A stack that maintains an increasing (or decreasing) order from bottom to top. Useful for "next greater element" and histogram problems.
Next Greater Element
For each element in an array, find the next element to its right that's greater.
def next_greater(arr):
result = [-1] * len(arr)
stack = [] # indices of elements waiting for a greater neighbor
for i, x in enumerate(arr):
while stack and arr[stack[-1]] < x:
result[stack.pop()] = x
stack.append(i)
return result
O(n). Each index is pushed and popped at most once. The stack stays monotonically decreasing (top is smallest).
Largest Rectangle in Histogram
Classic monotonic stack problem.
def largest_rectangle(heights):
stack = []
best = 0
heights = heights + [0] # sentinel to flush the stack
for i, h in enumerate(heights):
while stack and heights[stack[-1]] >= h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
best = max(best, height * width)
stack.append(i)
return best
The stack keeps indices of increasing heights. When a smaller height arrives, pop rectangles that can extend up to here.
When Each Pattern Applies
Pattern Signal
Two pointers Sorted input, pair sums, in-place transforms
Sliding window Contiguous subarray/substring, "longest/shortest/max
sum satisfying X"
Backtracking Combinations, permutations, puzzles, "all valid X"
Prefix sums Many range queries, subarray sums
Monotonic stack "Next greater/smaller", histogram-like problems
In an interview, pattern matching is half the battle. Spot the shape, pick the pattern.
Combining Patterns
Real problems often combine patterns.
Three Sum: sort the array, then for each i, use two pointers on the rest.
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo + 1]: lo += 1
while lo < hi and nums[hi] == nums[hi - 1]: hi -= 1
lo += 1; hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return result
O(n^2). Sort + two pointers. Pattern composition is common.
Common Pitfalls
Two pointers on unsorted data. Usually wrong. Sort first, or rethink.
Sliding window with wrong shrink condition. The loop that shrinks the window is where bugs live. Test on small cases.
Backtracking without undo. If you forget pop(), state leaks into sibling branches.
Prefix sums with wrong boundary. Off-by-one on prefix[hi + 1] - prefix[lo]. Trace a small example.
Monotonic stack in the wrong direction. Decreasing for "next greater", increasing for "next smaller". Mix them up and your answer is inverted.
Next Steps
Continue to 12-best-practices.md for the habits that turn algorithm knowledge into problem-solving skill.