← All patterns
Two Pointers
Two indices walk the data from both ends (or at two speeds) to prune pairs.
Reach for it when
- Input is sorted, or sorting it is allowed
- Pair / triplet with a target sum, or a palindrome check
- In-place compaction (remove duplicates, move zeroes)
Core idea
In a sorted array, if nums[l] + nums[r] is too small, no pair using l with anything left of r can work, so l moves right; if too big, r moves left. Each step discards a whole row of candidate pairs, collapsing O(n²) to O(n).
Template · O(n) time after an O(n log n) sort, O(1) extra space
def pair_with_sum(nums, target): # nums sorted l, r = 0, len(nums) - 1 while l < r: s = nums[l] + nums[r] if s == target: return [l, r] if s < target: l += 1 # need a bigger sum else: r -= 1 # need a smaller sum return []vector<int> pairWithSum(const vector<int>& nums, int target) { // nums sorted int l = 0, r = (int)nums.size() - 1; while (l < r) { int s = nums[l] + nums[r]; if (s == target) return {l, r}; if (s < target) l++; // need a bigger sum else r--; // need a smaller sum } return {};}Common pitfalls
- Forgetting to skip duplicates in 3Sum-style problems
- Using l <= r when a pair needs two distinct indices
- Sorting destroys original indices: keep (value, index) pairs if needed