Two Pointers and Sliding Window
Chapter 23: Two Pointers and Sliding Window
You have a sorted array and need to find two numbers that add up to a target. The brute-force approach tries every pair — O(n²). But if you place one pointer at the start and another at the end, you can solve it in a single pass. This is the two-pointer technique: by maintaining invariants about what lies between, before, or after the pointers, you eliminate vast swaths of the search space without checking them.
The sliding window is its close cousin. When the problem asks about a contiguous subarray or substring that satisfies some property, you can maintain a "window" — defined by left and right pointers — and grow or shrink it efficiently. Both techniques transform O(n²) brute force into O(n) elegance, and both share a single underlying principle: monotonic progress guarantees correctness without exhaustive search.
Level 1 · What You Need to Know
1.1 Three Pointer Patterns
Two-pointer problems fall into three distinct categories. Recognizing which pattern applies is 80% of solving the problem.
| Pattern | Pointer Movement | Typical Problems | Key Invariant |
|---|---|---|---|
| Fast-slow | Both start at head, fast moves 2x | Cycle detection, find middle, palindrome list | Fast reaches end ⟹ slow is at middle |
| Collision (opposite direction) | One at start, one at end, move inward | Two sum (sorted), three sum, container with water | Everything outside pointers is eliminated |
| Same-direction (sliding window) | Both start at left, right expands | Longest substring, minimum window, subarray sum | Window maintains some feasibility property |
Why three patterns and not one? Because the search space geometry differs. In collision pointers, you're searching over pairs (i, j) where i < j in a sorted structure — moving inward exploits sort order. In fast-slow, you're exploiting the difference in traversal speed to detect structural properties (cycles, midpoints). In sliding windows, you're searching over contiguous ranges, and the key insight is that when you advance the right pointer, you never need to move the left pointer backward (Klee, "Measuring the Intersection of Geometric Objects", 1977 — though the technique predates formal publication).
1.2 Fast-Slow Pointers
Floyd's Cycle Detection
The most famous fast-slow pointer algorithm. Given a linked list that may contain a cycle, determine if a cycle exists and find where it starts.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head: ListNode) -> bool:
"""Detect if linked list has a cycle. O(n) time, O(1) space."""
slow = fast = head
while fast and fast.next:
slow = slow.next # moves 1 step
fast = fast.next.next # moves 2 steps
if slow == fast:
return True
return False
def find_cycle_start(head: ListNode) -> ListNode:
"""Find the node where the cycle begins. Returns None if no cycle."""
slow = fast = head
# Phase 1: Detect cycle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # No cycle
# Phase 2: Find entry point
# Reset one pointer to head, advance both at speed 1
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
Why does Phase 2 work? Let the distance from head to cycle start be a, the distance from cycle start to the meeting point be b, and the cycle length be c. When slow and fast meet:
- slow traveled:
a + b - fast traveled:
a + b + k·c(for some integer k ≥ 1) - Since fast moves 2x:
2(a + b) = a + b + k·c→a + b = k·c→a = k·c - b
This means: walking a steps from the meeting point lands you at the cycle start (because you complete k full cycles minus the b steps you already took into the cycle). Walking a steps from the head also lands you at the cycle start. So both pointers meet exactly at the cycle entry.
Find Middle of Linked List
def find_middle(head: ListNode) -> ListNode:
"""Return the middle node. For even length, returns second middle."""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
When fast reaches the end (or one past the end), slow is at the middle. For a list of length n: fast takes ⌊n/2⌋ iterations of two steps, so slow takes ⌊n/2⌋ single steps — landing on position ⌊n/2⌋ (0-indexed), which is the middle (or second middle for even-length lists).
Palindrome Linked List
Combines find-middle with in-place reversal:
def is_palindrome(head: ListNode) -> bool:
"""Check if linked list is a palindrome. O(n) time, O(1) space."""
if not head or not head.next:
return True
# Find middle
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev = None
curr = slow.next
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Compare halves
first, second = head, prev
while second:
if first.val != second.val:
return False
first = first.next
second = second.next
return True
1.3 Collision Pointers (Opposite Direction)
Two Sum in Sorted Array (LeetCode #167)
def two_sum_sorted(numbers: list[int], target: int) -> list[int]:
"""Find two numbers in sorted array that sum to target.
Returns 1-indexed positions."""
left, right = 0, len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1]
elif current_sum < target:
left += 1 # Need larger sum → move left pointer right
else:
right -= 1 # Need smaller sum → move right pointer left
return [] # No solution found
Why this works (correctness proof): Consider the n×n matrix M where M[i][j] = numbers[i] + numbers[j]. Because the array is sorted, this matrix is sorted both row-wise and column-wise. The two-pointer technique performs a staircase walk through this matrix — starting at top-right corner (i=0, j=n-1). Moving left decreases the sum; moving down increases it. This visits at most 2n-1 cells and is guaranteed to find the target if it exists, because the staircase partitions the matrix into "too small" (below-left) and "too large" (above-right) regions, and the target must lie on the boundary between them.
Three Sum (LeetCode #15)
def three_sum(nums: list[int]) -> list[list[int]]:
"""Find all unique triplets that sum to zero."""
nums.sort()
result = []
for i in range(len(nums) - 2):
# Skip duplicates for first element
if i > 0 and nums[i] == nums[i - 1]:
continue
# Early termination: smallest possible sum > 0
if nums[i] > 0:
break
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
# Skip duplicates for second element
while left < right and nums[left] == nums[left + 1]:
left += 1
# Skip duplicates for third element
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
Complexity: Sorting is O(n log n). The outer loop runs n times, inner two-pointer scan is O(n) per iteration. Total: O(n²). This is optimal for Three Sum — Grønlund and Pettie proved in "Threesomes, Degenerates, and Love Triangles" (FOCS 2014) that under certain computational models, sub-quadratic Three Sum is possible but the practical improvement is marginal.
Container With Most Water (LeetCode #11)
def max_area(height: list[int]) -> int:
"""Find two lines that together with x-axis form container with most water."""
left, right = 0, len(height) - 1
best = 0
while left < right:
width = right - left
h = min(height[left], height[right])
best = max(best, width * h)
# Move the shorter side inward
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
Why move the shorter side? The area is min(h[left], h[right]) × (right - left). When you move either pointer inward, the width decreases by 1. If you move the taller side inward, the height cannot increase (it's still bounded by the shorter side), so the area strictly decreases — no point in exploring those options. By moving the shorter side, the height might increase enough to compensate for the width loss. This greedy choice eliminates O(n) suboptimal options at each step without missing the optimal pair.
1.4 Sliding Window Template
The sliding window technique maintains a range [left, right) (or [left, right]) that satisfies some constraint, and systematically explores all valid windows.
Fixed-Size Window
When the window size k is given, simply maintain a window of exactly k elements:
def max_sum_subarray(nums: list[int], k: int) -> int:
"""Maximum sum of subarray with exactly k elements."""
n = len(nums)
if n < k:
return 0
# Initialize first window
window_sum = sum(nums[:k])
best = window_sum
# Slide: add right element, remove left element
for right in range(k, n):
window_sum += nums[right] - nums[right - k]
best = max(best, window_sum)
return best
Variable-Size Window (Universal Template)
This is the template you'll use for 90% of sliding window problems:
def sliding_window_template(s: str) -> int:
"""
Universal sliding window template for variable-size windows.
The key insight: we expand the window (move right) to explore,
and shrink the window (move left) to restore a feasibility constraint.
Template works for:
- Longest substring/subarray satisfying condition → track max length
- Shortest substring/subarray satisfying condition → track min length
"""
from collections import defaultdict
window = defaultdict(int) # Window state (e.g., character counts)
left = 0
result = 0 # or float('inf') for minimum problems
for right in range(len(s)):
# 1. EXPAND: Add s[right] to window state
window[s[right]] += 1
# 2. SHRINK: While window violates the constraint, shrink from left
while window_is_invalid(window): # Replace with actual condition
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
left += 1
# 3. UPDATE: Current window [left, right] is valid, update answer
result = max(result, right - left + 1) # For longest
# result = min(result, right - left + 1) # For shortest
return result
1.5 Classic Sliding Window Problems
Longest Substring Without Repeating Characters (LeetCode #3)
def length_of_longest_substring(s: str) -> int:
"""Find length of longest substring without repeating characters.
Example: "abcabcbb" → 3 ("abc")
Approach: Maintain a window where all characters are unique.
When a duplicate enters, shrink from left until it's removed.
"""
char_index = {} # char → its most recent index in window
left = 0
max_length = 0
for right in range(len(s)):
# If character already in window, jump left past its previous position
if s[right] in char_index and char_index[s[right]] >= left:
left = char_index[s[right]] + 1
char_index[s[right]] = right
max_length = max(max_length, right - left + 1)
return max_length
Why the >= left check? Without it, we might jump left backward. The character might exist in char_index from a position before the current window's left boundary — that's not actually a duplicate within our window.
Minimum Window Substring (LeetCode #76)
def min_window(s: str, t: str) -> str:
"""Find minimum window in s that contains all characters of t.
Example: s = "ADOBECODEBANC", t = "ABC" → "BANC"
Approach: Expand right to include all chars of t, then shrink left
to find minimum. This is the 'find shortest valid window' pattern.
"""
from collections import Counter
if not s or not t:
return ""
# Count characters needed
need = Counter(t)
missing = len(t) # Number of chars still needed
# Result tracking
start = 0
min_len = float('inf')
left = 0
for right in range(len(s)):
# Expand: add s[right] to window
if need[s[right]] > 0:
missing -= 1
need[s[right]] -= 1
# Shrink: while window contains all of t, try to minimize
while missing == 0:
# Update result
window_len = right - left + 1
if window_len < min_len:
min_len = window_len
start = left
# Remove s[left] from window
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return s[start:start + min_len] if min_len != float('inf') else ""
The clever counting trick: Instead of maintaining two counters and comparing them (expensive), we track a single missing variable. It decreases when we add a truly needed character, and increases when we remove one. The window is valid exactly when missing == 0. This reduces the per-step overhead from O(|charset|) comparison to O(1).
Level 2 · How It Works
2.1 Universal Sliding Window Template (Detailed)
Every variable-size sliding window problem follows this structure. The differences between problems lie in three choices:
- What state does the window maintain? (Counter, sum, set, monotone deque)
- What is the validity condition? (All chars present, no duplicates, sum ≤ k)
- Are we maximizing or minimizing the window?
def universal_sliding_window(arr, constraint):
"""
Detailed universal template with extensive annotations.
INVARIANT: At every point in the algorithm, the window [left, right)
either satisfies the constraint or we are actively shrinking to restore it.
CORRECTNESS ARGUMENT:
- We consider every possible right endpoint (outer loop ensures this).
- For each right endpoint, we find the optimal left endpoint.
- The optimal left endpoint is monotonically non-decreasing
(this is the key insight that makes O(n) possible).
WHY O(n) TOTAL:
- The right pointer advances exactly n times (once per outer iteration).
- The left pointer advances at most n times total across ALL iterations
(it never moves backward, and can't exceed n total moves).
- Each element enters the window exactly once (when right passes it)
and leaves exactly once (when left passes it).
- Total operations: at most 2n pointer moves = O(n).
"""
n = len(arr)
left = 0
window_state = initialize_state() # Problem-specific
result = initial_result() # 0 for max, inf for min
for right in range(n):
# ─── STEP 1: EXPAND ───────────────────────────────────
# Add arr[right] to the window state.
# This might violate the constraint.
update_state_add(window_state, arr[right])
# ─── STEP 2: SHRINK ───────────────────────────────────
# Restore the constraint by advancing left.
# For LONGEST valid window: use "while invalid, shrink"
# For SHORTEST valid window: use "while valid, record and shrink"
while not is_valid(window_state, constraint):
update_state_remove(window_state, arr[left])
left += 1
# ─── STEP 3: RECORD ───────────────────────────────────
# Window [left, right] is now valid (for longest problems).
# Record if this is the best window seen so far.
result = max(result, right - left + 1)
return result
Critical subtlety: longest vs. shortest. For "longest valid window" problems, we shrink until valid, then record. For "shortest valid window" problems (like minimum window substring), we record while valid, then shrink:
# Shortest valid window variant:
for right in range(n):
update_state_add(window_state, arr[right])
while is_valid(window_state, constraint):
result = min(result, right - left + 1) # Record INSIDE the while
update_state_remove(window_state, arr[left])
left += 1
2.2 Why Sliding Window is O(n): A Rigorous Argument
Many students intuitively feel the nested while loop makes this O(n²). Here's why it's actually O(n):
Amortized analysis (aggregate method): Define a potential function Φ = left. Initially Φ = 0. Each iteration of the outer loop (advancing right) increases Φ by at most some amount via the inner while loop. But left can never exceed n, and left never decreases. Therefore:
- Total advances of
right: exactly n - Total advances of
left: at most n (since left ∈ [0, n] and never decreases) - Total pointer moves: ≤ 2n
Each pointer move does O(1) work (update a counter, compare values). Therefore total work is O(n).
Alternatively (accounting method): Assign each element a "budget" of 2 operations: one for being added to the window (when right passes it) and one for being removed (when left passes it). Each element is added exactly once and removed at most once. Total operations ≤ 2n = O(n).
This amortized argument was formalized by Tarjan in "Amortized Computational Complexity" (SIAM Journal on Algebraic and Discrete Methods, 1985), though the sliding window technique itself had been used earlier in various contexts.
2.3 Floyd's Cycle Detection: Complete Mathematical Proof
Theorem (Floyd, 1967): If a sequence x₀, x₁, x₂, ... defined by xᵢ = f(xᵢ₋₁) is eventually periodic, then there exist integers μ (the start of the cycle) and λ (the cycle length) such that xᵢ = xᵢ₊λ for all i ≥ μ. Both μ and λ can be found using O(1) space and O(μ + λ) time.
Proof of Phase 1 (meeting):
Let μ = distance from start to cycle entry, and λ = cycle length.
When slow enters the cycle (after μ steps), fast has taken 2μ steps, so fast is μ steps into the cycle, i.e., at position μ mod λ within the cycle.
The gap between fast and slow within the cycle is μ mod λ. But since fast gains 1 step per iteration, they meet after λ - (μ mod λ) additional iterations.
Total steps for slow to reach meeting point: μ + (λ - μ mod λ). Meeting point within cycle: (λ - μ mod λ) mod λ.
Proof of Phase 2 (finding μ):
At the meeting point, slow has traveled μ + (λ - μ mod λ) = μ + λ - (μ mod λ) steps.
The meeting point is at distance (λ - μ mod λ) from the cycle start (measuring forward in the cycle).
Now: distance from meeting point back to cycle start (going forward) = λ - (λ - μ mod λ) = μ mod λ.
Distance from head to cycle start = μ = qλ + (μ mod λ) for some integer q.
So walking μ steps from the meeting point means: (μ mod λ) steps to reach cycle start, then q full cycles back to cycle start. You end up at the cycle start.
Walking μ steps from the head also ends at the cycle start.
Therefore, when both pointers move at speed 1 from their respective starting positions (head and meeting point), they meet at the cycle start after exactly μ steps. ∎
Space complexity: O(1) — only two pointer variables. Time complexity: Phase 1 takes O(μ + λ) steps. Phase 2 takes O(μ) steps. Total: O(μ + λ).
2.4 Collision Pointer Correctness Proof
Claim: For the two-sum problem on a sorted array, the collision pointer technique finds a pair summing to the target if one exists.
Proof by invariant:
Let the array be a[0] ≤ a[1] ≤ ... ≤ a[n-1] and suppose a[i*] + a[j*] = target where i* < j*.
Invariant: At every step, i* ≥ left and j* ≤ right.
Base case: Initially left = 0 ≤ i* and j* ≤ n-1 = right. ✓
Inductive step: Suppose the invariant holds. Consider the current sum S = a[left] + a[right].
Case 1: S = target. We found it. Done.
Case 2: S < target. We increment left. Need to show i* ≥ left + 1, i.e., i* ≠ left.
Suppose for contradiction that i* = left. Then a[i*] + a[right] = a[left] + a[right] = S < target = a[i*] + a[j*]. This implies a[right] < a[j*]. Since the array is sorted and j* ≤ right, we have a[j*] ≤ a[right] — contradiction. Therefore i* > left, so i* ≥ left + 1. ✓
Case 3: S > target. Symmetric argument shows j* < right, so j* ≤ right - 1. ✓
Since the invariant is maintained, the algorithm cannot terminate without finding the solution (because we exit only when left ≥ right, but the invariant guarantees left ≤ i* < j* ≤ right, meaning left < right holds throughout). ∎
Key takeaway: The proof shows that each pointer movement provably eliminates an entire row or column from the search space — not by checking them, but by mathematical reasoning about the sort order.
2.5 Complexity Analysis of Classic Problems
| Problem | Time | Space | Why |
|---|---|---|---|
| Two Sum (sorted) | O(n) | O(1) | Each pointer moves at most n times |
| Three Sum | O(n²) | O(1) extra | O(n) outer × O(n) inner two-pointer |
| Container With Most Water | O(n) | O(1) | Each pointer moves at most n/2 times |
| Longest Substring (no repeat) | O(n) | O(min(n, | Σ |
| Minimum Window Substring | O(n + m) | O( | Σ |
| Floyd's Cycle Detection | O(μ + λ) | O(1) | Proof in 2.3 |
Level 3 · What the Spec Says
3.1 Floyd's Cycle Detection: Historical Context
Robert W. Floyd published the tortoise-and-hare algorithm in his 1967 unpublished note "Nondeterministic Algorithms" (the algorithm is sometimes attributed to this note, though the full details appeared in Knuth's "The Art of Computer Programming", Vol. 2, 1969, Exercise 6 in Section 3.1).
The algorithm was developed in the context of pseudo-random number generator testing. If a PRNG has internal state of size s bits, its period cannot exceed 2ˢ. Floyd's algorithm can detect the actual period using only O(1) extra memory — critical when the state space is enormous.
Brent's improvement (1980): Richard Brent proposed a modification ("An Improved Monte Carlo Factorization Algorithm", BIT Numerical Mathematics, 1980) that finds the cycle length λ directly in Phase 1. Instead of moving both pointers simultaneously, Brent's algorithm moves only the fast pointer and periodically teleports the slow pointer to the fast pointer's position. This finds the cycle 36% faster on average (the constant improves from 3μ + 3λ to approximately 2.4μ + 2.4λ evaluations of f).
def brent_cycle_detection(f, x0):
"""Brent's cycle detection. Returns (lambda, mu).
f: the function defining the sequence (x_i = f(x_{i-1}))
x0: starting value
Improvement over Floyd's: ~36% fewer function evaluations.
(Brent, 'An Improved Monte Carlo Factorization Algorithm', BIT 1980)
"""
# Phase 1: Find cycle length lambda
power = lam = 1
tortoise = x0
hare = f(x0)
while tortoise != hare:
if power == lam: # Time to reset
tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1
# Phase 2: Find cycle start mu
tortoise = hare = x0
for _ in range(lam):
hare = f(hare)
mu = 0
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare)
mu += 1
return lam, mu
3.2 Sliding Window and Monotone Queue Relationship
The sliding window technique handles problems where you need to maintain aggregate information (sum, count of distinct elements, character frequencies) over a moving range. But what if you need the maximum or minimum within the window?
Naively checking all elements in the window gives O(nk) for a window of size k. The monotone deque (covered in Chapter 6) provides O(n) total by maintaining a decreasing (or increasing) sequence of candidates:
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
"""Maximum in each sliding window of size k.
Uses monotone decreasing deque: front is always the max.
Elements that can never be the max are discarded.
Connection to two-pointer: the deque's front and back
act as implicit "pointers" into the window, with the
invariant that the deque stores indices of elements in
decreasing order of value.
See Chapter 6 for full monotone queue theory.
"""
dq = deque() # Stores indices
result = []
for i in range(len(nums)):
# Remove elements outside window
while dq and dq[0] <= i - k:
dq.popleft()
# Maintain decreasing order: remove smaller elements from back
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()
dq.append(i)
# Window is full: record the max (front of deque)
if i >= k - 1:
result.append(nums[dq[0]])
return result
The relationship: Both sliding window and monotone deque exploit the same principle — when the window slides right, some previously useful information becomes irrelevant (elements that left the window) and can be discarded in O(1) amortized time. The difference is what "useful" means: for sum problems, every element contributes equally; for max/min problems, elements dominated by newer, larger elements are useless.
3.3 Two Pointers in Sorting Algorithms
Two-pointer logic appears at the heart of two fundamental sorting algorithms:
Quicksort partition (Hoare's scheme, 1962):
def hoare_partition(arr: list, low: int, high: int) -> int:
"""Hoare's original two-pointer partition scheme.
Two pointers start at opposite ends and move toward each other.
Left pointer finds elements >= pivot; right finds elements <= pivot.
They swap when both find misplaced elements.
This is collision pointer technique applied to partitioning.
(C.A.R. Hoare, 'Quicksort', The Computer Journal, 1962)
"""
pivot = arr[low]
i = low - 1
j = high + 1
while True:
i += 1
while arr[i] < pivot:
i += 1
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
Merge sort's merge step (von Neumann, 1945):
def merge(left: list, right: list) -> list:
"""Merge two sorted arrays using same-direction two pointers.
Both pointers move left-to-right through their respective arrays.
At each step, take the smaller element and advance that pointer.
This is same-direction pointer technique on two separate sequences.
(John von Neumann, first described merge sort in 1945)
"""
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
Dutch National Flag (three-way partition, Dijkstra 1976):
A three-pointer variant used in quicksort to handle many duplicate elements efficiently:
def dutch_national_flag(arr: list, pivot) -> tuple:
"""Three-way partition: elements < pivot, == pivot, > pivot.
Three pointers: low, mid, high.
- [0, low): less than pivot
- [low, mid): equal to pivot
- [mid, high]: unexamined
- (high, n-1]: greater than pivot
(E.W. Dijkstra, 'A Discipline of Programming', 1976, Chapter 14)
"""
low = mid = 0
high = len(arr) - 1
while mid <= high:
if arr[mid] < pivot:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1
mid += 1
elif arr[mid] == pivot:
mid += 1
else:
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
return low, mid # Boundaries of the three partitions
3.4 Formal Analysis: When Can Two Pointers Be Applied?
Two pointers work when the search space has monotonic structure. Formally:
Condition for collision pointers: Given a function f(i, j) defined on pairs where i < j, collision pointers work if:
- f is non-decreasing in j for fixed i (or equivalently, non-decreasing in i for fixed j)
- You can determine from f(i, j) vs. target whether to advance i or retreat j
Condition for sliding window: Given a window property P([left, right]), sliding window works if:
- Monotonicity of feasibility: If P([left, right]) is infeasible (too much), then P([left, right+1]) is also infeasible (adding elements never helps when you have too much)
- Equivalently: if P([left, right]) is feasible, then P([left+1, right]) is also feasible (removing elements preserves feasibility)
This is sometimes called the "two-pointer condition" or "sliding window condition" in competitive programming literature (Laaksonen, "Competitive Programmer's Handbook", 2017).
Level 4 · Edge Cases and Pitfalls
4.1 Common Boundary Errors
Off-by-One in Window Size
# WRONG: Window size is right - left, not right - left + 1
# when using [left, right) convention
length = right - left # Correct for half-open [left, right)
length = right - left + 1 # Correct for closed [left, right]
# Choose one convention and stick with it!
# Half-open [left, right) is generally safer because:
# - Empty window: left == right (clean check)
# - Window size: right - left (no +1)
# - Iteration: for i in range(left, right) works directly
Empty Array / Single Element
def two_sum_safe(nums: list[int], target: int) -> list[int]:
"""Always handle edge cases first."""
if len(nums) < 2:
return [] # Can't form a pair
left, right = 0, len(nums) - 1
while left < right: # NOT left <= right (would compare element with itself)
# ... normal logic
pass
return []
The left < right vs left <= right mistake: For pair-finding problems, you must use left < right (strict) because a single element can't pair with itself. Using <= leads to either infinite loops or counting an element twice.
All Elements Identical
# Three sum with all zeros: [0, 0, 0, 0, 0]
# Without deduplication: returns [0,0,0] many times
# The skip-duplicate logic handles this:
if i > 0 and nums[i] == nums[i-1]:
continue # Skip duplicate first element
# But be careful: skip AFTER recording, not before checking
# WRONG:
while left < right and nums[left] == nums[left + 1]:
left += 1
left += 1 # Need this extra advance!
# If you forget the final left += 1, you stay on the same value
4.2 Character Counting Pitfalls in Sliding Window
Counter vs. Plain Dict
from collections import Counter
# PITFALL 1: Counter allows negative values silently
c = Counter("abc")
c['a'] -= 5 # c['a'] is now -4, no error raised!
# This is actually USEFUL for sliding window (see min_window above),
# but you must understand the semantics:
# - Positive count: we still need this many
# - Zero count: exactly satisfied
# - Negative count: we have more than needed (surplus)
# PITFALL 2: Comparing dicts/Counters is O(|alphabet|)
# DON'T do this every iteration:
if window_counter == need_counter: # O(26) for lowercase, O(128) for ASCII
# ...
# DO maintain a running "satisfied" count instead:
# Track how many DISTINCT characters have reached their required count.
# This gives O(1) validity checks.
The "formed" Variable Pattern
def find_anagrams(s: str, p: str) -> list[int]:
"""LeetCode #438: Find all start indices of p's anagrams in s.
Key insight: Instead of comparing two Counters each step (O(26)),
track how many characters have the exact required count.
"""
if len(p) > len(s):
return []
from collections import Counter
need = Counter(p)
window = Counter()
result = []
# 'formed' = number of unique chars in window matching required count
formed = 0
required = len(need) # Number of unique chars in p
for right in range(len(s)):
char = s[right]
window[char] += 1
# Check if this char's count NOW matches
if char in need and window[char] == need[char]:
formed += 1
# Shrink if window too large
if right >= len(p):
left_char = s[right - len(p)]
if left_char in need and window[left_char] == need[left_char]:
formed -= 1
window[left_char] -= 1
# Check if all chars match
if formed == required:
result.append(right - len(p) + 1)
return result
4.3 Interview Problems in Detail
Minimum Size Subarray Sum (LeetCode #209)
def min_subarray_len(target: int, nums: list[int]) -> int:
"""Find minimal length subarray with sum >= target.
All elements are positive (crucial assumption!).
This means: as we expand right, sum increases; as we shrink left, sum decreases.
Monotonicity is guaranteed by positive elements.
WARNING: This does NOT work if elements can be negative.
For arrays with negatives, use prefix sums + binary search (O(n log n)).
"""
n = len(nums)
left = 0
current_sum = 0
min_length = float('inf')
for right in range(n):
current_sum += nums[right]
# Shrink while valid (finding shortest)
while current_sum >= target:
min_length = min(min_length, right - left + 1)
current_sum -= nums[left]
left += 1
return min_length if min_length != float('inf') else 0
Why positive elements matter: If elements can be negative, adding more elements might decrease the sum, and removing elements might increase it. The monotonicity assumption (expanding always increases, shrinking always decreases) breaks down, and the left pointer might need to move backward — violating the O(n) guarantee.
Longest Repeating Character Replacement (LeetCode #424)
def character_replacement(s: str, k: int) -> int:
"""Longest substring where you can replace at most k characters
to make all characters the same.
Key insight: A window of length L is valid if:
L - max_count <= k
where max_count is the count of the most frequent char in the window.
Meaning: the number of chars we need to replace (L - max_count)
must be at most k.
"""
from collections import defaultdict
count = defaultdict(int)
left = 0
max_count = 0 # Max frequency of any single char in current window
max_length = 0
for right in range(len(s)):
count[s[right]] += 1
max_count = max(max_count, count[s[right]])
# Window invalid: too many chars need replacing
window_len = right - left + 1
if window_len - max_count > k:
count[s[left]] -= 1
left += 1
max_length = max(max_length, right - left + 1)
return max_length
Subtle optimization: We never decrease max_count when shrinking the window. This seems wrong — when the most frequent character leaves the window, shouldn't max_count decrease?
The key insight: we only care about finding a longer valid window than our current best. A window can only be longer if it has a higher max_count (since the validity condition is window_len - max_count ≤ k, a longer valid window requires max_count to have grown). So we never need to shrink max_count — if the current max_count doesn't lead to a longer window, we simply don't update max_length. This is why we use if (shrink by exactly 1) instead of while (shrink until valid): we maintain the window at a fixed size, only growing it when max_count increases.
This clever trick was popularized by competitive programmers and is attributed to various contest solutions from the mid-2010s.
Find All Anagrams in a String (LeetCode #438)
See the implementation in Section 4.2 above. Additional notes:
def find_anagrams_simple(s: str, p: str) -> list[int]:
"""Alternative: Fixed-size window with sorted/Counter comparison.
Simpler to understand but slightly less efficient due to
Counter comparison at each step.
"""
from collections import Counter
k = len(p)
if k > len(s):
return []
p_count = Counter(p)
window_count = Counter(s[:k])
result = []
if window_count == p_count:
result.append(0)
for i in range(k, len(s)):
# Add new character
window_count[s[i]] += 1
# Remove old character
old_char = s[i - k]
window_count[old_char] -= 1
if window_count[old_char] == 0:
del window_count[old_char] # Important: remove zero entries!
if window_count == p_count:
result.append(i - k + 1)
return result
Why del window_count[old_char] when count reaches 0? Python's Counter.__eq__ considers Counter({'a': 1, 'b': 0}) != Counter({'a': 1}). Zero-count entries are not automatically removed. If you don't delete them, comparisons will fail. This is the #1 bug in sliding window implementations using Counter comparison.
4.4 Three Sum Deduplication: The Correct Approach
Deduplication in Three Sum is the source of more interview bugs than almost any other aspect of the problem. Here's the correct approach and common mistakes:
def three_sum_dedup_analysis(nums: list[int]) -> list[list[int]]:
"""Detailed analysis of correct deduplication in Three Sum."""
nums.sort()
result = []
for i in range(len(nums) - 2):
# CORRECT: Skip duplicate first elements
# Check i > 0 to avoid index out of bounds
# Compare with PREVIOUS, not NEXT
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
# CORRECT: Skip duplicates AFTER recording the solution
# Move past ALL duplicates of nums[left]
while left < right and nums[left] == nums[left + 1]:
left += 1
# Move past ALL duplicates of nums[right]
while left < right and nums[right] == nums[right - 1]:
right -= 1
# THEN move one more step (past the last duplicate)
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
# COMMON MISTAKE 1: Skipping duplicates BEFORE checking
# This can skip valid solutions:
# WRONG: if nums[left] == nums[left+1]: left += 1; continue
# This skips without ever checking if current left forms a solution!
# COMMON MISTAKE 2: Forgetting the final left += 1 / right -= 1
# After the while loops skip duplicates, you're ON the last duplicate.
# You need one more step to move past it.
# COMMON MISTAKE 3: Using a set to store results
# three_sum_set.add(tuple(sorted(triplet))) # Works but O(1) extra per result
# This is considered poor form in interviews — the interviewer wants
# to see you handle deduplication algorithmically.
4.5 When NOT to Use Two Pointers
Two pointers are not universally applicable. Knowing when they don't work is as important as knowing when they do.
Unsorted Array Two Sum
# Two Sum (LeetCode #1): Find indices of two numbers summing to target.
# Array is NOT sorted.
# WRONG approach: sorting + two pointers
# Sorting loses the original indices! You'd need to store (value, index)
# pairs, sort by value, then extract indices — works but awkward.
# CORRECT approach: Hash map, O(n) time, O(n) space
def two_sum_unsorted(nums: list[int], target: int) -> list[int]:
"""For unsorted arrays, use a hash map, not two pointers."""
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
# WHY two pointers fail here:
# 1. No sort order → no monotonic invariant → can't decide which pointer to move
# 2. Sorting costs O(n log n), hash map is O(n) — worse time complexity
# 3. Sorting destroys index information (the problem asks for indices)
Subarray Sum with Negative Numbers
# Subarray sum equals k (LeetCode #560): Array may contain negatives.
#
# WRONG: Sliding window
# With negatives, extending the window might decrease the sum,
# and shrinking might increase it. No monotonicity!
#
# Example: nums = [1, -1, 1, -1, 1], k = 0
# Window [0,1] sums to 0 ✓, but sliding window logic can't find [0,3] = 0
# CORRECT: Prefix sum + hash map
def subarray_sum(nums: list[int], k: int) -> int:
"""Count subarrays summing to k. Works with negative numbers."""
from collections import defaultdict
count = 0
prefix_sum = 0
# Map: prefix_sum value → number of times it's occurred
prefix_counts = defaultdict(int)
prefix_counts[0] = 1 # Empty prefix
for num in nums:
prefix_sum += num
# If prefix_sum - k existed before, those subarrays sum to k
count += prefix_counts[prefix_sum - k]
prefix_counts[prefix_sum] += 1
return count
Non-Contiguous Subsequences
Two pointers / sliding window are for contiguous subarrays. If the problem asks about subsequences (not necessarily contiguous), you typically need dynamic programming or other techniques.
# Longest Increasing Subsequence: NOT a two-pointer problem
# Longest Common Subsequence: NOT a two-pointer problem
# These require DP because elements can be non-adjacent
# EXCEPTION: Two-pointer on two sorted arrays for merge/intersection
# works because both sequences are traversed in order
4.6 Performance Comparison: Two Pointers vs. Alternatives
| Problem | Two Pointers | Alternative | When to Choose Alternative |
|---|---|---|---|
| Two Sum (sorted) | O(n), O(1) space | Binary search: O(n log n) | Never — two pointers is strictly better |
| Two Sum (unsorted) | O(n log n) after sort | Hash map: O(n), O(n) space | When indices needed or n is very large |
| Subarray sum ≥ k (positive) | O(n) | Prefix + binary search: O(n log n) | Never — sliding window is better |
| Subarray sum = k (with negatives) | N/A | Prefix + hash: O(n) | Always — two pointers don't work |
| Longest substring (condition) | O(n) | Brute force: O(n²) or O(n³) | Never — sliding window dominates |
| Cycle detection | O(μ+λ), O(1) space | Hash set: O(μ+λ), O(μ+λ) space | When O(1) space is not required |
4.7 Debugging Checklist for Two-Pointer Problems
When your solution fails on edge cases, check these in order:
-
Initialization: Are left and right starting at the correct positions? (0 and n-1 for collision; both 0 for same-direction)
-
Loop condition:
left < right(pair problems) vs.left <= right(search problems) vs.right < n(sliding window) -
Update order: In sliding window, always expand first, then check validity, then shrink. Getting the order wrong causes off-by-one errors.
-
Pointer movement after match: In Three Sum, after finding a valid triplet, you must advance BOTH pointers (not just one). Otherwise you either miss solutions or generate duplicates.
-
Empty input / single element: Always handle
len(nums) < 2(or whatever minimum makes sense) as a special case before the main loop. -
Integer overflow: In languages with fixed-width integers (C, Java),
nums[left] + nums[right]might overflow. Use(long)nums[left] + nums[right]or check before adding. -
Window state cleanup: When removing an element from the window, check if its count reaches 0 and clean it up (delete from dict/Counter). Stale zero-count entries cause subtle comparison bugs.
# Complete debugging example: minimum window substring
def min_window_debug(s: str, t: str) -> str:
"""Version with extensive assertions for debugging."""
from collections import Counter
if not s or not t or len(s) < len(t):
return ""
need = Counter(t)
missing = len(t)
left = 0
start, min_len = 0, float('inf')
for right in range(len(s)):
if need[s[right]] > 0:
missing -= 1
need[s[right]] -= 1
assert missing >= 0, "missing should never go negative"
while missing == 0:
window_len = right - left + 1
assert window_len >= len(t), "valid window can't be shorter than t"
if window_len < min_len:
min_len = window_len
start = left
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
assert left <= right + 1, "left can't pass right"
return s[start:start + min_len] if min_len != float('inf') else ""
4.8 Summary of Key Patterns
┌─────────────────────────────────────────────────────────────────┐
│ TWO POINTERS DECISION TREE │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Is the array/list SORTED (or can you sort it)? │
│ ├── YES: Is the problem about PAIRS (i,j)? │
│ │ ├── YES → COLLISION POINTERS (left=0, right=n-1) │
│ │ └── NO → Consider binary search instead │
│ └── NO: Is it about CONTIGUOUS subarrays/substrings? │
│ ├── YES: Is there MONOTONICITY in the constraint? │
│ │ ├── YES → SLIDING WINDOW │
│ │ └── NO → Use prefix sums + hash map │
│ └── NO → Hash map or DP (two pointers won't work) │
│ │
│ Is it a LINKED LIST problem? │
│ ├── Cycle detection → FAST-SLOW (Floyd's) │
│ ├── Find middle → FAST-SLOW │
│ ├── k-th from end → two pointers with k gap │
│ └── Merge/intersect → same-direction pointers │
│ │
└─────────────────────────────────────────────────────────────────┘
Final thought: Two pointers and sliding window are not just "tricks" — they are manifestations of a deeper algorithmic principle. When your search space has monotone structure, you can replace exhaustive enumeration with guided traversal. The O(n²) → O(n) reduction comes not from cleverness but from understanding the mathematical properties of your problem. Every time you write a two-pointer solution, ask yourself: what invariant makes it safe to never move a pointer backward? If you can answer that, your solution is correct. If you cannot, it probably isn't.