DSA Patterns
Two Pointers
Why does comparing the two ends of a sorted array discard an entire family of pairs at once? Brute force checks every (i, j). Sortedness turns one comparison into a safe half-plane cut.
Two pointers are useful when a proves many candidates impossible, or when one index scans while another maintains a compacted boundary. The speedup is the proof, not the second variable.
What happens first?
Problem shape
Sorted pair, compaction, merge, or relative speed?
Can one comparison eliminate a whole region?
Pointer invariant
What region or prefix is already settled?
Why must the active region shrink every step?
What actually happens
Naive idea: try every pair (or nest three loops for 3Sum). Correct on tiny n. At n = 10⁵, Θ(n²) pair checks are about 10¹⁰ operations: past a typical contest budget.
Better idea: when the sequence is ordered, place pointers at both extremes. If the sum is too small, proves the left value cannot pair with anyone still active; move left. Symmetrically for a sum that is too large. The invariant: if an answer exists and none has been returned, it still lies in [L, R].
The improved design still fails on unsorted two-sum (use a hash map instead), when sorting would destroy required original indices, when every valid pair must be emitted and output is Θ(n²), or when a branch fails to make .
Invariant (sorted pair sum)
If the original input contains a valid pair and none has been returned yet, a valid pair still exists entirely inside [left, right]. Each move must preserve that claim. Monotonicity is required: without sorted order, discarding a side is unjustified.
How to choose two pointers
1. Is there ordered evidence? Opposite-end discard needs sortedness or another monotone relation. Unsorted exact pair-sum prefers a hash map without changing index order.
2. Contiguous compaction or merge? Use for in-place filter/dedupe. Use one pointer per sorted input for merge and intersection.
3. Relative speed on a list? Slow/fast exposes midpoints and cycles. That is still two pointers, but the invariant is about distance and topology, not sorted discard.
Quantitative check
Sorted pair sum: each pointer moves at most n times, so O(n) after sorting. Sort + scan is O(n log n). 3Sum after sorting: fix one index and run a linear two-pointer scan on the suffix, O(n²) instead of O(n³). At n = 10³ that is about 10⁶ vs 10⁹ inner steps.
Recognize the shape
Look for an ordering, boundary, or relative-speed relationship. Then ask whether a local comparison rules out an entire row or column of the brute-force search space.
Strong signals
- A sorted sequence and a pairwise target, distance, or symmetry condition.
- An in-place, stable transform: remove duplicates, move zeros, filter values.
- Two sorted inputs that must be merged, intersected, or compared.
- A linked list asking about a cycle, midpoint, or kth node from the end.
Pause before using it
- On unsorted two-sum, a hash map gives O(n) without changing index order.
- If moving a pointer cannot eliminate anything, the rule is only a guess.
- If every valid pair must be emitted, the output itself may be Θ(n²).
- Sorting is not free when original indices or input order are part of the answer.
Relationship to sliding window: a sliding window is a same-direction two-pointer pattern whose pointers delimit a contiguous interval and maintain an aggregate. Not every two-pointer problem has a window.
Interactive: movement must have a reason
In the first mode, watch a single comparison remove a family of pairs. Then switch to read/write mode to see how a correct output prefix grows without extra storage.
Pointer movement laboratory
Step through both major shapes. Notice that a pointer moves only after an invariant proves what can be discarded.
Sorted pair sum · target 10
Step 1 / 4
Left value
nums[0] = -7
Current comparison
6 < 10
Right value
nums[6] = 13
The sum is too small, so advance the left pointer.
Why this is safe: -7 + 13 is the largest sum possible with -7. Since even that is below 10, every pair using index 0 is impossible.
Candidate region
21
of 21
pairs remain
Invariant: if a solution exists, one remains entirely inside [L, R].
The four common arrangements
1. Opposite ends
L starts at 0 and R at n − 1. Sortedness or symmetry tells you which boundary is impossible.
Examples: Pair sum, palindrome, max area, trapping variants
2. Read / write
Read examines every item; write marks the next output slot or the end of a valid prefix.
Examples: Deduplicate, filter, move zeros, stable partition
3. One per sequence
Each pointer tracks the smallest unconsumed value in one ordered input.
Examples: Merge, intersection, subsequence checks
4. Different speeds
Fast gains on slow at a known rate, turning distance or cyclic structure into a meeting condition.
Examples: Floyd cycle detection, middle node, happy number
Canonical example: sorted pair sum
Given a sorted array, find left < right such that the two values sum to target. Start at both extremes because they expose the smallest and largest active values ().
Python
def pair_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return left, right
if total < target:
left += 1 # nums[left] was too small
else:
right -= 1 # nums[right] was too large
return NoneJava
final class PairSumSorted {
static int[] findPair(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
long total = (long) nums[left] + nums[right];
if (total == target) return new int[] {left, right};
if (total < target) {
left++; // nums[left] was too small
} else {
right--; // nums[right] was too large
}
}
return null;
}
}Initialization
Before the loop, every legal pair lies in [left, right] because that interval is the whole array.
Maintenance
If the sum is low, even the largest partner cannot rescue nums[left]; the high case symmetrically rules out nums[right].
Termination
Each iteration moves one boundary inward. Equality returns a pair; left ≥ right proves no two distinct active indices remain.
Same direction: build a correct prefix
For a sorted array, duplicates are adjacent. Let read inspect each value while write is the length of the unique prefix. Only new values cross the boundary.
Python
def dedupe_sorted(nums):
if not nums:
return 0
write = 1
for read in range(1, len(nums)):
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return write # answer is nums[:write]Java
final class DedupeSorted {
static int dedupe(int[] nums) {
if (nums.length == 0) return 0;
int write = 1;
for (int read = 1; read < nums.length; read++) {
if (nums[read] != nums[write - 1]) {
nums[write] = nums[read];
write++;
}
}
return write; // answer is nums[0..write)
}
}Invariant
Before each iteration, nums[:write] contains exactly the unique values from the processed input, in their original order. Everything at or after write is disposable workspace.
Generalization
Replace the equality test with any keep(value) predicate. This gives a stable in-place filter: read always moves; write moves only when a value belongs in the output.
Lift the pattern: 3Sum
Sorting lets us fix one value and solve a two-sum problem on the suffix. This replaces three nested loops, O(n³), with one outer loop and a linear two-pointer scan, O(n²). Duplicate skipping belongs to the output contract, not to the pointer idea itself.
Python
def three_sum(nums):
nums.sort()
triples = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
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:
left += 1
elif total > 0:
right -= 1
else:
triples.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
return triplesJava
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
final class ThreeSum {
static List<List<Integer>> solve(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> triples = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
if (nums[i] > 0) break;
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
long total = (long) nums[i] + nums[left] + nums[right];
if (total < 0) {
left++;
} else if (total > 0) {
right--;
} else {
triples.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
}
}
}
return triples;
}
}Variant map: pointer meaning → invariant
| Problem shape | Arrangement | Movement rule | What remains true |
|---|---|---|---|
| Palindrome / near-palindrome | Opposite ends | Compare symmetric values; move both inward after a match. | Everything outside [L, R] has already matched. |
| Container with most water | Opposite ends | Record area, then move the pointer at the shorter wall. | Keeping the shorter wall while reducing width cannot improve its best area. |
| Remove / retain by predicate | Read + write | Read visits every item; write advances only when an item is kept. | The prefix before write is the correct stable output so far. |
| Merge two sorted sequences | One per input | Emit the smaller front value and advance only that input. | The output contains the globally smallest consumed values in order. |
| Linked-list middle / cycle | Slow + fast | Slow moves one edge; fast moves two. | Their relative motion exposes a midpoint or forces a meeting inside a cycle. |
Complexity: count pointer moves
A loop can contain two pointers and still be quadratic. The linear bound comes from proving that each pointer moves at most the length of its sequence and never moves backward.
Pair sum (sorted)
O(n)
Extra space: O(1)
Sort + pair sum
O(n log n)
Extra space: Sort-dependent
Stable compaction
O(n)
Extra space: O(1)
3Sum after sorting
O(n²)
Extra space: Sort-dependent
Sorting may use O(log n) stack space or O(n) auxiliary space depending on the language and implementation. Output storage is normally excluded from “extra space” but should be stated explicitly when it matters.
Edge cases that change the code
Empty or one-element input
Guard before seeding a write prefix; use left < right when a pair must use two distinct indices.
Duplicates
Decide whether duplicate values, duplicate index pairs, or only unique results are allowed. Skip only after recording a valid result.
Original indices
Sorting destroys positions. Sort (value, original_index) pairs, or use a hash map when indices are the required output.
Overflow
In fixed-width languages, promote before adding large values; three-sum and area products are especially easy to overflow.
Mutation contract
Read/write techniques overwrite the array. Return the valid length and document that values beyond it are unspecified.
Progress on every branch
Every non-returning loop path must move at least one pointer. Equality branches are a common source of infinite loops.
Simple rule of thumb
- What region or prefix does each pointer delimit?
- What invariant is true before and after every iteration?
- What candidates does each movement eliminate, and why can none be an answer?
- What guarantees progress, termination, and the requested duplicate/index semantics?
Exercises
- On
[1, 2, 4, 7, 11]and target 13, trace opposite-end moves. After each comparison, which pairs became impossible, and which invariant sentence still holds? - Unsorted two-sum needs original indices. When is sort + two pointers wrong for the stated contract, and what structure restores O(n) expected time?
- Give a counterexample where moving the shorter wall in “container with most water” would be incorrect if the height array were not indexed left-to-right as written. What property of width and min-height justifies the move?
Primary sources
- Cormen et al., Introduction to Algorithms (CLRS): two-pointer ideas in sorting merges and partition.
- Bentley, Programming Pearls: problem reduction and scanning with multiple indices.
- Classic statements: two-sum (sorted), 3Sum, container with most water, remove duplicates in-place.
Takeaway
Two pointers turn a two-dimensional search into a monotone walk when a movement rule is provably safe. State the pointer invariant, require monotonicity when you discard a region, and ensure every branch makes progress.