Pattern 01
Two Pointers
Use two positions whose movement can eliminate choices without checking every pair.
Recognize it
Read the constraints before choosing the technique
Sorted array or string
Order tells you which side can move without losing a solution.
Pair, palindrome, or comparison from both ends
The answer depends on two positions at once.
In-place or constant extra space
Two indices can replace a copied array or lookup table.
Cases that look similar but need another approach
The input is unsorted and original indices must be returned
Sorting would destroy the original positions; without order, the sum gives no safe movement rule.
Every pair must be produced
The output itself contains quadratic many pairs, so there is nothing to eliminate.
Items may be skipped arbitrarily as a subsequence
A steady inward scan cannot represent arbitrary choices and backtracking.
Reasoning
The ideas the code depends on
Sorted order supplies direction
For a sorted array, a sum below the target can only be increased by moving the left index right. A sum above the target can only be decreased by moving the right index left.
Movement needs a proof
Do not move a pointer because it “looks smaller.” State which entire group of pairs becomes impossible after the comparison.
There are two common layouts
Converging pointers start at opposite ends. Reader/writer pointers move in the same direction to edit an array in place.
Procedure
Turn the invariant into a repeatable process
- 01
Place the pointers where the search space begins, usually the first and last positions.
- 02
Measure the current pair against the goal.
- 03
If it is the answer, record or return it.
- 04
Otherwise move the one pointer whose current value cannot participate in a valid answer.
- 05
Stop when the pointers meet or cross.
Common forms of the pattern
Each pointer moves in only one direction and can cross at most n positions. No pair of pointer positions is revisited.
Implementation
Worked form
Sorted pair sum
Return the indices of two values in a sorted array whose sum equals target.
Sorted pair sum
int[] pairWithTarget(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return new int[]{left, right};
if (sum < target) left++;
else right--;
}
return new int[]{-1, -1};
}def pair_with_target(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
else:
right -= 1
return [-1, -1]vector<int> pairWithTarget(const vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return {left, right};
if (sum < target) left++;
else right--;
}
return {-1, -1};
}Common implementation mistakes
- Using the pattern on unsorted data without another source of direction
- Moving both pointers after a comparison and skipping candidates
- Returning values when the problem asks for indices
- Using <= in a loop that must never compare an item with itself
Problem family
What stays the same—and what changes
These are not five unrelated solutions. Each problem preserves the movement rule and changes one part of the state or answer.
Valid Palindrome
EasyCompare characters; skip characters the problem says to ignore.
Remove Duplicates In-Place
EasyUse reader and writer positions moving in the same direction.
Container With Most Water
MediumRecord area, then move the shorter side because it limits the result.
3Sum
MediumFix one number, then run a two-pointer search on the suffix.
Trapping Rain Water
HardCarry the highest boundary seen from each side.
Check yourself