Two Pointers
The two pointers technique uses two index variables to traverse a data structure — typically an array or string — in a way that reduces time complexity from O(n²) to O(n). It's one of the most frequently used patterns in coding interviews and real-world algorithms.
What Are Two Pointers?#
Instead of using nested loops to compare every pair of elements, two pointers move strategically through the data. Depending on the problem, the pointers might start at opposite ends and move inward, or both start at the left and one races ahead.
Real-World Analogies#
- Two People Searching a Bookshelf: One starts from the left, one from the right, meeting in the middle
- Speed and Slow Runners on a Track: A fast runner lapping a slow runner detects a cycle
- Accordion: Squeezing from both ends toward the center until you find the right note
- Merging Sorted Piles of Papers: One finger on each pile, always picking the smaller top page
Key Patterns#
| Pattern | Pointer Movement | Typical Problems |
|---|---|---|
| Opposite Direction | Start at both ends, move inward | Two Sum (sorted), Container With Most Water, Valid Palindrome |
| Sliding Window | Both start left, right expands/contracts | Longest Substring Without Repeating, Minimum Window Substring |
| Fast and Slow | Both start left, one moves faster | Linked List Cycle, Middle of Linked List, Happy Number |
| Merge Pattern | One pointer per sorted input | Merge Two Sorted Arrays, Intersection of Arrays |
Two Sum (Sorted Array)#
Problem: Given a sorted array and a target sum, find two numbers that add up to the target.
This is the sorted version of the classic Two Sum. With a sorted array, two pointers solve it in O(n) without a hash map.
Why Two Pointers Work#
Because the array is sorted, the sum of the two pointed-at elements tells us which pointer to move. If the sum is too large, moving the right pointer left decreases it. If too small, moving the left pointer right increases it. Each step eliminates one candidate, guaranteeing O(n) convergence.
Two Sum (Sorted)
Find two numbers in a sorted array that sum to target
Container With Most Water#
Problem: Given an array of heights, find two lines that together with the x-axis form a container holding the most water.
Why Two Pointers Work#
Start with the widest container (both ends). The area is min(height[L], height[R]) × (R - L). Moving inward always decreases width, so the only way to find a larger area is to find a taller shorter side. Moving the taller line inward can only decrease or maintain the minimum height — it can never help. Moving the shorter line is the only move that has a chance of increasing the area.
Container With Most Water
Find two lines forming the container with maximum area
Sliding Window: Longest Substring Without Repeating Characters#
Problem: Given a string, find the length of the longest substring without repeating characters.
The sliding window is a same-direction two-pointer pattern. The right pointer expands the window to include new characters; the left pointer contracts it when a duplicate is found.
Longest Substring Without Repeating Characters
Find the longest substring with all unique characters using sliding window
Fast and Slow Pointers: Linked List Cycle#
Problem: Determine if a linked list has a cycle. A cycle exists if a node can be reached again by following next pointers.
The fast-and-slow (Floyd's Tortoise and Hare) pattern uses two pointers that move at different speeds. If there's a cycle, the fast pointer will eventually lap the slow pointer.
Why It Works#
Think of two runners on a circular track. The fast runner (2 steps/turn) gains one position per turn on the slow runner (1 step/turn). If the track is circular, the fast runner will eventually come around and meet the slow runner. If the track is linear (no cycle), the fast runner will reach the end.
Linked List Cycle Detection
Detect if a linked list contains a cycle using Floyd's algorithm
Three Sum#
Problem: Given an array, find all unique triplets that sum to zero. This extends two-pointer to handle three elements by fixing one and running two-pointer on the rest.
Three Sum
Find all unique triplets summing to zero using sort + two pointers
Valid Palindrome#
Problem: Check if a string reads the same forwards and backwards, considering only alphanumeric characters and ignoring case.
A clean example of the opposite-direction pattern applied to strings.
Valid Palindrome
Check palindrome with two pointers from both ends
Choosing the Right Two-Pointer Pattern#
| If the problem says... | Use this pattern | Example |
|---|---|---|
| Sorted array + pair/triplet sum | Opposite direction | Two Sum, Three Sum |
| Substring/subarray with constraint | Sliding window | Longest substring, minimum window |
| Cycle detection or middle element | Fast and slow | Linked list cycle, happy number |
| Merge or compare sorted inputs | Merge pointers | Merge sorted arrays, intersection |
| Palindrome or symmetry check | Opposite direction | Valid palindrome, reverse check |
Reviewing AI-Generated Code#
What to Verify#
| Issue | What to Check | Common AI Mistake |
|---|---|---|
| Infinite loops | Both pointers always make progress | Missing pointer increment after finding a match |
| Boundary conditions | Pointer stays in bounds | Accessing index -1 or past array length |
| Duplicate handling | Skip duplicates after finding result | Missing duplicate skip in Three Sum |
| Window invariant | Left never passes right | Expanding window without proper contraction |
| Sorted assumption | Check if input must be sorted | Using opposite-direction on unsorted array |
Questions to Ask AI#
When AI generates two-pointer code, verify:
- "Do both pointers always move forward? Can we get stuck in an infinite loop?"
- "What happens when the array has duplicates?"
- "Is the array assumed to be sorted? What if it isn't?"
- "What's the window invariant, and is it maintained after every operation?"
Summary#
| Problem | Pattern | Time | Space | Key Insight |
|---|---|---|---|---|
| Two Sum (Sorted) | Opposite | O(n) | O(1) | Sum too big → move right left; too small → move left right |
| Container With Most Water | Opposite | O(n) | O(1) | Move the shorter line inward — it's the only way to find a larger area |
| Longest Substring | Sliding Window | O(n) | O(min(n,m)) | Expand right, shrink left when duplicate found |
| Linked List Cycle | Fast & Slow | O(n) | O(1) | Fast runner laps slow runner if cycle exists |
| Three Sum | Opposite + Loop | O(n²) | O(1) | Fix one element, two-pointer the rest; skip duplicates |
Key Takeaways#
- Two pointers turn O(n²) into O(n) — by eliminating redundant comparisons, one pass replaces nested loops
- Know the three families: opposite-direction (sorted arrays, palindromes), sliding window (substrings, subarrays), fast-and-slow (cycles, middle elements)
- Opposite-direction for sum problems requires sorted input — if the problem gives you a sorted array, two pointers should be your first thought; for palindromes and container problems, sorting is not needed
- Sliding window maintains an invariant — the window always represents a valid state; expand to grow, shrink to restore the invariant
- Duplicate skipping is critical — in problems like Three Sum, forgetting to skip duplicates produces wrong output, not just duplicates in the result