Two Pointers
- Build the two pointer mental model from first principles: pointer roles, invariant, movement rule, and proof
- Separate the main families: opposite direction, same direction, boundary greedy, three region partition, and fast and slow pointers
- Understand why sorted order lets one comparison eliminate many candidate pairs at once
- Use reader and writer pointers to modify arrays in place without extra space
- Reason through fast and slow pointer techniques for linked list middle, cycle detection, and cycle entry
- Avoid the common traps: unsorted input, wrong loop condition, duplicate handling, infinite loops, and unsafe pointer movement
- Use the guide as a reference later by reducing every two pointer task to four questions: what the pointers mean, what stays true, which pointer moves, and why that move is safe
Two pointers solves a search, comparison, or in-place transformation by coordinating two positions so that every pointer move safely eliminates work, finalizes part of the input, or reveals structure. A two pointer solution is not defined by the number of index variables. It is defined by whether each pointer has a responsibility and whether each movement can be justified without discarding a valid answer.
A pointer moves because the current state proves that keeping it would be useless, or because the value it points to has already been processed. Two pointer solutions turn brute force into linear time because the algorithm does not check every pair or every possible arrangement. It uses structure to skip entire groups of candidates.
What Two Pointers Actually Is
A brute force pair search checks every combination.
This is O(n²) because the algorithm has no way to skip groups of pairs. It tries one pair, learns almost nothing, then tries the next pair.
Two pointers is useful when one comparison can rule out more than one candidate. In a sorted array, the smallest remaining value is on the left, and the largest remaining value is on the right. If their sum is too small, the left value cannot work with any remaining right value because every other right value is smaller or equal to the current right. That group of pairs has been ruled out, so left can move.
If the sum is too large, the right value cannot work with any remaining left value because every other left value is larger or equal to the current left. That group of pairs has been ruled out, so right can move. The important property is that each comparison eliminates a full group of candidates, not just the current pair.
Sorted pair search is only one family. Other two pointer patterns use different responsibilities: in in-place array cleanup, one pointer reads and one pointer writes. In linked lists, one pointer moves faster than the other. In boundary optimization, two endpoints define a candidate, and one endpoint limits the score. The shared idea is that each pointer movement has a specific justification.
The Invariant
Every two pointer solution needs an invariant. An invariant is what stays true while the algorithm moves.
Sorted pair search
All candidates outside the current left to right search space have already been ruled out.
Reader and writer compaction
Everything before write is clean, final, and should not change.
Three region partitioning
The array is split into solved regions and one unknown region.
Fast and slow pointers
Fast has moved at a predictable speed relative to slow.
The invariant is the reason the code is short. Once the invariant is clear, each pointer move either preserves it, restores it, or uses it to finalize part of the answer. Without an invariant, pointer code becomes fragile. It might pass the obvious cases, but it fails when duplicates, boundaries, empty arrays, or even length lists appear.
Family 1: Sorted Pair Search
Opposite direction pointers start at both ends and move inward. This family is most useful when the input is sorted or when the two ends of the input have a special relationship. The classic setup is sorted pair search.
The important line is not the assignment. It is the reason the pointer is allowed to move. If total < target, the current left value is too small even when paired with the largest remaining value. Pairing it with anything smaller would also be too small. So the left value cannot participate in any answer, and moving left is safe.
If total > target, the current right value is too large even when paired with the smallest remaining value. Pairing it with anything larger would also be too large. So the right value cannot participate in any answer, and moving right is safe. That is why the algorithm does not miss the answer.
Start with pointers at opposite ends. Left points to the smallest value (1), right points to the largest (11).
Why Sorted Order Matters
Opposite direction pair search depends on sorted order. If the array is not sorted, a sum that is too small does not tell you which side to move. A bigger value might be anywhere. A smaller value might be anywhere. The pointer movement no longer has a proof.
For unsorted pair search where original indices matter, use a hash map.
Sorting can still be useful when the task asks for values rather than original indices, or when it asks for unique combinations. But once original indices matter, sorting either destroys the answer or requires extra bookkeeping.
Family 2: Symmetric Endpoints
Sometimes the two pointers are not searching for a sum. They are comparing symmetric positions. A palindrome check is the simplest version.
The invariant is: everything outside the current left to right range has already been matched. If the characters match, both endpoints are settled. They will never need to be examined again, so both pointers move inward. If they do not match, strict palindrome validation fails immediately.
For a version that allows one deletion, a mismatch is different. The algorithm is allowed to skip one character, but it does not know whether to skip the left character or the right character. Since neither move is forced, the algorithm checks both possibilities.
When a mismatch can be fixed by deleting either side, neither pointer movement is automatically justified. The algorithm must check both possible deletions because the comparison alone does not prove which side is safe to discard.
The endpoints are both r. They match, so both positions are settled.
Family 3: Boundary-Limited Choices
Boundary greedy problems use two endpoints to define a candidate. The pointer movement is based on which boundary limits the candidate. For a container style area task, the score is width times the shorter height. The shorter wall is the bottleneck.
If you move the taller wall inward, width decreases, and the height is still capped by the shorter wall. That cannot improve the score. The only move with potential is moving the shorter wall.
The proof is not sorted order. It is bottleneck elimination. For the current shorter wall, the current opposite wall gives the maximum possible width. Any future container using that same shorter wall would have less width and height no greater than the shorter wall. So that shorter wall has already had its best chance. It can be eliminated.
Full geometry walkthrough
The proof above explains why moving the shorter wall is safe. The walkthrough below shows the full algorithm running on a 9-bar array, with water fill, width tracking, and area computation at each step.
Container with Most Water
Start at opposite ends for maximum width. Area = min(height) * width, so the shorter wall is always the bottleneck.
Family 4: Reducing Larger Searches to Pair Search
Some tasks ask for three or more values, but sorting lets you fix one value and reduce the rest to pair search. The most common structure is: sort the array, fix one value with an outer loop, use opposite direction pointers on the remaining range, and skip duplicates so each value combination appears once.
The inner loop is the sorted pair search you already know. The outer loop chooses the fixed value. Duplicate handling is the part that usually causes mistakes.
You skip duplicate fixed values before starting a repeated inner search because all combinations starting with that same fixed value were already considered. After finding a valid combination, you skip duplicate left and right values because the next unique combination must use different values at those positions.
Fix first value at index 0 (value -1). Set left = 1, right = 4.
Family 5: Reader and Writer Pointers
Same direction pointers both move forward, but they have different responsibilities. Reader and writer pointers separate two jobs: the reader scans the input, and the writer marks where the next kept value should go. This family is used for in-place array changes with O(1) extra space.
The invariant
Everything before write is clean and final. Everything from write to read is disposable or not final. Everything from read onward has not been processed.
Removing a Value In Place
The reader examines every value. If the value should stay, the writer places it into the next clean slot. If the value should be removed, the reader simply moves on. The writer never gets ahead of the reader, so overwriting is safe. Any position before write contains a value the algorithm has chosen to keep.
Deduplicating a Sorted Array
Sorted order makes duplicates adjacent, so the reader only needs to compare the current value with the previous value.
Moving Values While Preserving Order
Every time the reader finds a nonzero value, that value belongs in the clean prefix. The writer points to the next position in that prefix. After the loop, every nonzero value has been moved forward in its original relative order. The zeroes naturally collect behind the clean prefix because they were skipped or swapped past.
Reader and writer both start at 0. The task is to remove all 3s in place.
Family 6: Three Region Partition
Some in-place tasks need more than a clean prefix. They need multiple solved regions. For values with three categories, use three pointers.
| Region | Meaning |
|---|---|
| Before low | Solved low values |
| low to before mid | Solved middle values |
| mid to high | Unknown values |
| After high | Solved high values |
The mid pointer examines the next unknown value.
The branch that needs the most care is the swap with the high side. When nums[mid] belongs to the high region and is swapped with nums[high], the value that arrives at mid came from the unknown region. It has not been inspected yet. That is why mid does not move in that branch.
When nums[mid] belongs to the low region, swapping with low is safe and mid moves because the incoming value came from the already processed middle region.
Three pointers: low = 0, mid = 0, high = 5. The entire array is unknown.
Family 7: Fast and Slow Traversal
Fast and slow pointers use different traversal speeds to reveal structure. This family appears most often in linked lists because linked lists do not allow random access. You cannot jump to an index. You have to discover structure through traversal.
Finding the Middle Node
Fast moves two steps while slow moves one. When fast reaches the end, slow has traveled about half as far, so it is at the middle.
Cycle Detection
If there is no cycle, fast reaches the end. If there is a cycle, fast eventually catches slow. Once both pointers are inside the cycle, fast gains one node per iteration relative to slow. In a finite cycle, that gap must eventually close.
Cycle Entry
After detecting that a cycle exists, you can find where it begins. Once slow and fast meet, reset one pointer to the head. Keep the other at the meeting point. Move both one step at a time. Their next meeting point is the cycle entry.
The full proof uses modular distance around the cycle, but the practical intuition is enough to remember the algorithm: the first meeting point aligns the remaining distance from head to entry with the distance from meeting point to entry. Moving both pointers at the same speed makes them arrive together.
Both pointers start at the head.
Full linked-list walkthrough
The conceptual visual above shows speed relationships. The walkthrough below renders an actual linked list with cycle topology, showing the exact node-by-node traversal as fast closes the gap on slow.
Linked List Cycle Detection
Both pointers start at the head. Slow moves 1 step, fast moves 2 steps.
Two Pointers vs Similar Patterns
Two pointers is often confused with sliding window, hash maps, and binary search.
Two Pointers vs Sliding Window
Sliding window maintains state over the entire range between the pointers. Two pointers usually cares about endpoint roles, writer position, solved regions, or traversal speeds.
| Question | Two Pointers | Sliding Window |
|---|---|---|
| What matters? | Pointer roles or endpoint values | Everything inside the range |
| State | Usually small or role-based | Sum, count, set, map, or deque |
| Movement | Eliminates, writes, partitions, or detects | Expands and shrinks to maintain validity |
| Example signal | Sorted pair, in-place removal, linked list cycle | Longest substring, at most k, minimum subarray |
If you need a running sum, frequency map, distinct count, or validity rule for every element between left and right, think sliding window. If the decision comes from the pointer positions themselves, think two pointers.
Two Pointers vs Hash Map
Use a hash map when lookup matters more than order. For unsorted pair search with original indices, the hash map is usually best because it finds complements directly. Use two pointers when sorted order lets you eliminate candidates.
Two Pointers vs Binary Search
Both can use sorted input, but they eliminate search space differently. Binary search asks whether the answer is left or right of a midpoint. Two pointers asks whether the current endpoint relationship proves one endpoint can move. For sorted pair search, two pointers is usually cleaner than doing binary search for every index because it turns the whole search into one sweep.
- •Pointer roles and safe movement
- •Sorted pair search, in-place cleanup
- •Decision based on endpoint values
- •Maintained state over a range
- •Substring, subarray with constraints
- •Decision based on aggregate range state
- •Direct O(1) lookup by key
- •Unsorted pair search, frequency counting
- •No ordering requirement
- •Midpoint elimination halves search space
- •Sorted search for a single target
- •Logarithmic narrowing per step
When This Pattern Breaks
A good reference must teach when not to use the pattern.
1. Unsorted input removes the movement proof
Opposite direction pair search needs sorted order or another monotonic property. Without it, moving a pointer is a guess. Use a hash map or sort if the task allows it.
2. The pointers are moving without responsibilities
If you cannot say what each pointer means, the solution is not ready. Weak reasoning sounds like "move left sometimes." Strong reasoning sounds like "left is the smallest remaining candidate."
3. A move that proves nothing may skip the answer
Every movement should either eliminate candidates, finalize a region, write a kept value, or reveal structure. If moving a pointer does not do one of those, the algorithm may skip answers.
4. The range needs aggregate state
If the task depends on every element between the pointers, two pointers may not be enough. Use sliding window when the important thing is the range state.
5. Duplicate values are being treated as distinct choices
Sorted combination tasks often need duplicate skipping. The safe rule is to process the first copy, then skip later copies that would produce the same result.
6. A branch can repeat the same state forever
Every branch must move a pointer or return an answer. If one branch does neither, the loop can run forever.
Debugging Two Pointer Code
Use this when your two pointer code fails hidden tests.
Does the movement rule require sorted input?
If yes, make sure the input is sorted or sort it safely.
Are you returning original indices?
Sorting changes positions. If original indices matter, use a hash map or store original indices before sorting.
Does every loop branch make progress?
Every non-return path should move at least one pointer.
Is the loop condition correct?
Use left < right when one element cannot be used twice. Use mid <= high when the middle pointer must process every unknown value. Use fast and fast.next before moving fast.next.next.
Are duplicates skipped at the correct time?
Skip duplicate fixed values before repeating a search. Skip duplicate moving values after recording a valid combination.
Is the writer invariant true?
Everything before write should be clean and final.
Did you advance mid after swapping with high?
If yes, check whether you skipped an unknown value.
Are you comparing linked list nodes by identity?
Use node references, not node values.
Deriving a Solution
When a two pointer problem feels unclear, derive the loop in this order.
Step 1: Define the pointer roles
| Pointer | Role |
|---|---|
| left | Smallest remaining candidate |
| right | Largest remaining candidate |
| read | Current value being inspected |
| write | Next clean output position |
| low | End of low-value solved region |
| mid | Current unknown value |
| high | Start of high-value solved region |
| slow | One-step traversal |
| fast | Two-step traversal |
Step 2: State the invariant
| Family | Invariant |
|---|---|
| Opposite direction | Candidates outside the current range are ruled out |
| Reader and writer | Everything before write is final |
| Three region | Solved regions surround the unknown region |
| Fast and slow | Fast moves at a fixed speed relative to slow |
Step 3: Define the movement rule
| Situation | Movement |
|---|---|
| Sorted sum too small | Move left |
| Sorted sum too large | Move right |
| Value should be kept | Write it, then move write |
| Value belongs to low region | Swap with low, then move low and mid |
| Value belongs to high region | Swap with high, then move high only |
| Fast reaches end | Slow is at the middle |
| Fast meets slow | Cycle exists |
Step 4: Prove the move is safe
This is the step most people skip. Do not say "because that is the template." Say what was eliminated, finalized, written, or detected.
Step 5: Prove termination
The search space shrinks. The reader reaches the end. The unknown region disappears. Fast reaches null or meets slow. A two pointer algorithm should always have visible progress.
Reference Templates
Family Recap
Eliminating an endpoint
In sorted pair search, the left pointer holds the smallest remaining candidate and the right pointer holds the largest. When their sum is too small, the left value has already failed with the best possible partner, so every pair using that value can be removed from the search.
This reasoning depends on sorted order. Without sorted input, the comparison no longer proves which side should move.
Settling symmetric positions
In palindrome checks, the left and right pointers compare mirrored positions. When they match, both endpoints are settled and cannot affect the remaining comparison. Both pointers move inward because there is nothing left to learn from those positions.
When one deletion is allowed, a mismatch does not immediately prove which character to skip. The algorithm must try both possibilities.
Removing a limiting boundary
In container problems, the two pointers define the edges of a candidate. The shorter wall caps the height, and the current width is already the maximum for that wall. Any future container using the same short wall would have less width and the same height cap. Moving the shorter boundary is the only action that might improve the result.
Moving the taller wall instead can only decrease the area, because width shrinks while height stays limited by the shorter side.
Building a clean prefix
In in-place removal and deduplication, the reader scans every value while the writer marks the next position in the finalized output. Everything before the writer is correct and will not change. The writer never gets ahead of the reader, so overwriting earlier positions is always safe.
If the writer advances without the reader finding a value worth keeping, the prefix invariant breaks.
Classifying unknown values
In three-way partitioning, the pointers divide the array into solved regions and one unknown region. Each step examines the value at the middle pointer and swaps it into the correct solved region. The unknown region shrinks by one value every step.
After swapping with the high side, the value that arrives at the middle pointer came from the unknown region and has not been examined. Advancing the middle pointer would skip it.
Using speed difference
In linked list traversal, the slow pointer moves one node per step while the fast pointer moves two. When fast reaches the end, slow is at the middle. When both enter a cycle, fast gains one node per step on slow and must eventually catch it.
Comparing node values instead of node references is a common mistake. Two different nodes can hold the same value.
If the task does not fit any of these forms, it is probably not a two pointer problem. If you need aggregate state across the entire range between the pointers, think sliding window. If you need unsorted pair lookup with original indices, think hash map.
Rebuilding the Pattern
When you return to two pointers after time away, the fastest way to recover the pattern is not to remember whether the code used left, right, read, write, slow, or fast. The fastest way is to ask what each pointer means.
In sorted pair search, the pointers represent the smallest and largest remaining candidates. The movement rule comes from sorted order. If the sum is too small, the left value cannot work with any remaining right value, so moving left is safe. If the sum is too large, the right value cannot work with any remaining left value, so moving right is safe. The algorithm is linear because each move eliminates an endpoint from the remaining search space.
In reader and writer tasks, the pointers have different roles. The reader scans the input, while the writer marks the next position in the clean output prefix. The important invariant is that everything before the writer has already been chosen and finalized. Once that invariant is clear, in-place removal, deduplication, and compaction all become variations of the same idea.
In partitioning tasks, the pointers are not just two moving positions. They are boundaries between solved regions and unknown regions. The code becomes easier to reason about when each region has a label. The most common bug comes from advancing the middle pointer after swapping with the high side, even though the value that arrived from the high side has not been examined yet.
In fast and slow pointer tasks, the pointers represent a speed relationship rather than a range or output position. Moving one pointer twice as fast lets the algorithm find a midpoint, detect a cycle, or locate a cycle entry without extra memory. The proof comes from distance: fast either reaches the end, or inside a cycle it eventually catches slow.
A good two pointer solution is built from four decisions: what each pointer represents, what remains true as the pointers move, which movement rule applies, and why that movement does not discard a valid answer. If any of those decisions is unclear, the code may still look familiar, but it is probably being copied rather than derived.
Check Your Understanding
Use these questions to check whether you can reason through the pattern without looking at the template.
Take Assessment
15 questions covering all seven two pointer families.
Practice this pattern
Apply the guide to complete interview problems with explanations and code.
Learn Two Pointers in a guided sequence
The Interview Course connects this pattern to its prerequisites, worked lessons, and progressively harder problems.