Two Pointers

Core Concepts

Two pointers — a technique using two index variables on a sequence to reduce brute-force O(n²) traversal to O(n) or O(n log n) by exploiting structure (sorted order, monotonicity, or pointer-speed difference) to eliminate unnecessary comparisons.

Opposite-direction pointers — left starts at index 0, right at n−1; they converge inward. Works when the structure is sorted or has a symmetric property that lets you decide which pointer to advance without checking every pair.

Same-direction pointers (fast/slow) — both start at the same end; fast always advances, slow advances conditionally. Used for in-place filtering, cycle detection, or finding positional relationships in linked lists.

Two-sequence pointers — one pointer per sequence, both advancing forward. Used when merging or comparing two sorted arrays or strings.

Search space invariant — the key correctness property: at every step, if a valid answer exists, it lies within the current [left, right] window or has already been found. Each pointer move eliminates an entire row or column of the implicit O(n²) search space.

---

Structural Invariants

---

Types / Variants

---

Key Algorithms

Opposite-Direction: Target Sum on Sorted Array

Given sorted arr and target t: if arr[l] + arr[r] < t, advance l; if greater, retreat r; if equal, found. Insight: sorted order means advancing l can only increase the sum, retreating r can only decrease it — one pointer move eliminates an entire row of the n×n grid. O(n) time, O(1) space.

Opposite-Direction: Container With Most Water

Advance the pointer at the shorter side. Insight: moving the taller side cannot increase area (width shrinks, height is still bounded by the shorter side), so moving the shorter side is the only chance to find a larger area. O(n) time.

Dutch National Flag (3-Color Partition)

Three pointers: lo, mid, hi. mid scans forward; swap arr[mid] with arr[lo] if it belongs to group 0 (advance both), swap with arr[hi] if it belongs to group 2 (retreat hi only, don't advance mid — the swapped element is unexamined). O(n) time, O(1) space.

lo, mid, hi = 0, 0, len(arr) - 1
while mid <= hi:
    if arr[mid] == 0: arr[lo], arr[mid] = arr[mid], arr[lo]; lo += 1; mid += 1
    elif arr[mid] == 2: arr[mid], arr[hi] = arr[hi], arr[mid]; hi -= 1
    else: mid += 1

Same-Direction: Read/Write In-Place Removal

write marks the next valid insertion index; read scans every element. When arr[read] passes the keep condition, write it at arr[write] and increment write. O(n) time, O(1) space.

k-Sum (k ≥ 3): Fix Outer + Two-Pointer Inner

Sort. Outer loop fixes element at index i; inner two-pointer solves (k−1)-Sum on the suffix [i+1, n−1]. Recurse for k > 3. Skip duplicate values at each level immediately after processing to avoid duplicate tuples. O(n^(k−1)) time.

Floyd's Cycle Detection (Fast/Slow on Linked List)

Cycle detection: fast moves 2 steps, slow moves 1. They meet inside the cycle iff one exists. Cycle entry: reset one pointer to head; advance both 1 step at a time — they meet at the entry node. Insight: distance from head to entry equals distance from meeting point to entry (mod cycle length). O(n) time, O(1) space.

Middle of Linked List

Fast moves 2 steps, slow moves 1. When fast reaches the end, slow is at the middle. For even-length lists: while fast and fast.next stops with slow at the first middle; while fast.next and fast.next.next stops with slow at the second middle.

kth Node From End

Advance fast k steps ahead, then move both 1 step at a time. When fast reaches the end, slow is at the kth node from the end. O(n) time.

Trapping Rain Water

Use opposite-direction pointers. Maintain left_max and right_max. The side with the smaller max is the binding constraint — water at that pointer = max − current height. Advance that pointer inward. O(n) time, O(1) space.

l, r, lmax, rmax, res = 0, len(h)-1, 0, 0, 0
while l < r:
    if h[l] < h[r]: lmax = max(lmax, h[l]); res += lmax - h[l]; l += 1
    else: rmax = max(rmax, h[r]); res += rmax - h[r]; r -= 1

Two-Sequence Pointer: Subsequence Check

Advance both pointers; advance the sequence pointer only when characters match. If the subsequence pointer reaches the end, it is a subsequence. O(n + m) time.

---

Advanced Techniques

Two Pointers After Sorting a Transformed Array

Solves: problems where the natural order is non-monotonic (e.g., squares of a sorted array with negatives). Sort or transform to restore monotonicity, then apply opposite-direction pointers. Mechanism: squares of a sorted array are smallest in the middle and largest at the edges — use two outward-converging pointers filling the result from the back. When to use over simpler alternatives: only when a direct scan is non-monotonic but a transformation makes it monotonic. Don't apply when the original array is already monotone after the operation. O(n) vs O(n log n) naive sort.

Binary Search + Two Pointers Hybrid

Solves: problems where you want to count or find pairs satisfying a condition, and one pointer can jump rather than step (e.g., "number of pairs with product < k" in a sorted array). Mechanism: fix the left pointer; binary search for the furthest valid right pointer. Accumulate counts from entire ranges rather than advancing one step at a time. When to use over pure two pointers: when the answer is a count (not a pair), and the valid right boundary is a contiguous suffix — then binary search on that boundary is cleaner. Don't use when you need to enumerate all pairs. O(n log n) vs O(n²) brute force.

Slow/Fast Pointer for Linked List Restructuring

Solves: finding the start of the second half (reorder list, palindrome linked list check, sort list merge point). Mechanism: find middle via fast/slow, then reverse the second half in-place, then process both halves together. When to use over naive: any time you need O(1) extra space on a linked list structural problem. Don't use when O(n) space (stack or array copy) is acceptable and the constant factor matters more than memory. O(n) time, O(1) space.

Multi-Pointer for Interval / Window Problems

Solves: problems with more than two independent boundaries (e.g., partition into three parts, 3-color sort with extra constraints). Mechanism: each pointer owns one boundary of a partition; each element is routed to the correct partition by which pointer claims it. When to use over sorting: only when you need in-place O(n) — sorting is O(n log n) and requires the elements to be orderable. Don't use when comparisons are complex enough to make pointer logic error-prone.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• while left < right vs while left <= right: use < for opposite-direction (left == right is a single element, not a valid pair); use <= right for same-direction when all positions must be visited. Using <= in opposite-direction causes out-of-bounds or double-counting on the last step.

• Unsorted input with opposite-direction pointers: the search-space elimination relies entirely on sorted order. Applying opposite-direction to an unsorted array is incorrect; sort first or switch to a hash map approach.

• Skipping duplicates in 3Sum — wrong position: the skip loop must run after recording the valid triplet, not before reaching the inner two-pointer. Skipping before means you miss valid triplets that start or end on a duplicate boundary.

• Fast pointer null check: always check fast and fast.next (not just fast) before advancing two steps. Checking only fast causes fast.next.next to throw when fast is the last node.

• Dutch National Flag: don't advance mid after swapping with hi: the element swapped from hi is unexamined; advancing mid would skip it. After a swap with lo, both lo and mid advance because the element coming from lo was already classified (it is 1, since mid only swaps non-zero values to lo).

• Integer overflow in sum: not an issue in Python, but in Java/C++ arr[l] + arr[r] can overflow if values are large. Use long or compare arr[r] == target - arr[l].

• Off-by-one in "fill from back" patterns: when merging two sorted arrays into the first, the loop condition is p1 >= 0 or p2 >= 0; forgetting to drain the remaining elements of the longer array is a common incomplete termination.

• Modifying the array during a two-pointer scan: writing to positions that the read pointer hasn't reached yet is safe in the read/write pattern because write ≤ read is a maintained invariant. Breaking this invariant (e.g., swapping elements far behind) can clobber unread data.

---

Implementation Notes

• Python list supports O(1) index access; no extra considerations for two-pointer index arithmetic.
• For linked list fast/slow, always use while fast and fast.next not while fast.next — the latter throws on an empty list.
• When sorting before two pointers, the sort cost O(n log n) dominates; the two-pointer pass is O(n). Total is O(n log n).
• arr[write] = arr[read] is a self-assignment when write == read — this is safe and doesn't need a special-case branch.
• Returning arr[:write] after read/write in-place removal gives the valid prefix without copying in Python; LeetCode in-place problems typically want write as the return value (the new length), not a slice.
• For the "intersection of two linked lists" pattern, cycle both pointers through both lists: when they reach the end of their list, redirect to the head of the other. They will meet at the intersection after at most O(m + n) steps, with no extra space.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Opposite-direction on sorted array

• Two Sum II — Input Array Is Sorted (Easy)
• Valid Palindrome (Easy)
• Container With Most Water (Medium)
• Trapping Rain Water (Hard)

k-Sum

• Two Sum (Easy — hash map version, not two-pointer, but the conceptual anchor)
• 3Sum (Medium)
• 3Sum Closest (Medium)
• 4Sum (Medium)

In-place removal and partitioning

• Remove Duplicates from Sorted Array (Easy)
• Move Zeroes (Easy)
• Sort Colors / Dutch National Flag (Medium)
• Remove Duplicates from Sorted Array II (Medium)

Linked list positional problems

• Linked List Cycle (Easy)
• Middle of the Linked List (Easy)
• Remove Nth Node From End of List (Medium)
• Linked List Cycle II — cycle entry (Medium)
• Reorder List (Medium)
• Palindrome Linked List (Medium)

Two-sequence

• Merge Sorted Array (Easy)
• Is Subsequence (Easy)
• Squares of a Sorted Array (Easy)

Hard / combined

• Minimum Window Substring (sliding window, not pure two-pointer — but tests the same pointer advance intuition)
• Intersection of Two Linked Lists (Easy rating, non-trivial O(1)-space idea)

Additional LeetCode Coverage

• Find the Celebrity (LC 277)
• Duplicate Zeros (LC 1089)
• Max Number of K-Sum Pairs (LC 1679)
• Rearrange Array Elements by Sign (LC 2149)
• Total Cost to Hire K Workers (LC 2462)

Clarification Questions to Ask

• Is the input array sorted, or can I sort it? (determines whether opposite-direction is valid)
• Are elements unique, or can there be duplicates? (determines whether duplicate-skipping logic is needed)
• For k-Sum: should I return indices or values? Can the same element be used twice?
• For "in-place": is returning the new length sufficient, or must elements after the new length be specific values?
• For linked list: can I modify node values, or only node links? Is there a guaranteed tail?
• For palindrome: does "valid palindrome" mean ignore non-alphanumeric characters and case?

Common Interview Mistakes

• Forgetting to sort the array before applying opposite-direction two pointers, then wondering why it misses pairs.
• In 3Sum, returning immediately after the first valid triplet instead of continuing, or not deduplicating and returning duplicate triplets.
• Advancing both lo and hi pointers simultaneously when only one should move (e.g., in Dutch National Flag after swapping with hi).
• Using while left <= right for opposite-direction — this causes the two pointers to collide on a single element, incorrectly treating a single element as a valid pair.
• Forgetting fast.next null check on linked lists; the code crashes on even-length lists or single-node lists.
• Writing to a position the read pointer hasn't passed yet, breaking the read/write invariant and corrupting unread data.

Typical Follow-Up Escalations

• "Now the array isn't sorted — can you still do it in O(n)?" → use a hash set/map instead of two pointers; O(n) time, O(n) space trade-off.
• "Now find all unique triplets instead of just one" → add duplicate-skipping loops at both the outer and inner levels.
• "Now the input is a stream (online)" → two pointers require random access; switch to a hash map or sort the stream as it arrives.
• "Can you do this with O(1) extra space?" → usually means two pointers or in-place Dutch National Flag; articulate the invariant you're maintaining.
• "What if there are multiple valid answers — return the count?" → instead of stopping on the first valid pair, accumulate; for sorted arrays with duplicates, multiply counts by the number of valid right-pointer positions using combinatorics.