Two pointers
easyOn sorted data, 'the sum is too small' means the left pointer can move right with certainty - discarding every pair involving the old left value. n²/2 candidates become n steps.
O(n)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How two pointers works
The brute force checks every pair - n²/2 candidates on an array of n. Two pointers starts at both ends of a sorted array and asks one question per step: is a[lo] + a[hi] below or above the target? Below means a[lo] cannot reach the target even with the largest remaining partner, so every pair involving a[lo] dies with a single increment of lo.
Sortedness is the whole licence. On sorted data, too small means move lo with certainty; on unsorted data the same move discards pairs that might have worked. If you cannot sort - because the problem wants original indices, say - the alternative is a hash set, which trades O(n) memory for the ordering.
Recognition signals: sorted input (or input that is free to sort), a question about pairs or a converging range, and a comparison that can rule out many candidates at once. The linear bound comes from one-way movement: lo only rises, hi only falls, and they meet after at most n total steps.
Step by step
- Search 2, 5, 9, 13, 18 for a pair summing to 22. lo starts at index 0 (value 2), hi at index 4 (value 18).
- a[0] + a[4] = 2 + 18 = 20 - short by 2. No partner can lift 2 to the target, so lo advances to 1.
- a[1] + a[4] = 5 + 18 = 23 - over by 1. Every remaining partner for 18 overshoots, so hi drops to 3.
- a[1] + a[3] = 5 + 13 = 18, still short of 22. Discard 5 as well: lo advances to 2.
- a[2] + a[3] = 9 + 13 = 22. That is the target - return the pair of indices (2, 3).
- Four comparisons settled a five-element array. The double loop would have tried up to 10 pairs, and that gap widens quadratically with n.
Complexity
| Worst case time | O(n) |
|---|---|
| Space | O(1) |
Reference implementation
Python
def two_sum_sorted(a, target):
"""O(n) instead of the O(n^2) double loop - because a is sorted."""
lo, hi = 0, len(a) - 1
while lo < hi:
s = a[lo] + a[hi]
if s == target:
return lo, hi
if s < target:
lo += 1 # only a bigger left value can help
else:
hi -= 1 # only a smaller right value can help
return NoneJavaScript
function twoSumSorted(a, target) {
let lo = 0, hi = a.length - 1;
while (lo < hi) {
const s = a[lo] + a[hi];
if (s === target) return [lo, hi];
if (s < target) lo++; else hi--;
}
return null;
}Java
static int[] twoSumSorted(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo < hi) {
int s = a[lo] + a[hi];
if (s == target) return new int[]{lo, hi};
if (s < target) lo++; else hi--;
}
return null;
}Worth noticing
Each step eliminates a whole row of the brute force
The double loop checks every pair - n²/2 of them. When the sum is too small, moving `lo` right discards every pair involving the old `lo`, because none of them can be larger. One comparison rules out n candidates.
It only works because the array is sorted
Sortedness is what makes 'too small' mean 'move left pointer' with certainty. On unsorted data the same move discards pairs that might have worked - you would need a hash set instead, trading O(n) memory for the ordering.
The pointers never turn around
`lo` only rises, `hi` only falls, and they meet in the middle. Total movement is exactly n, which is where the linear bound comes from - the same accounting that makes sliding windows linear.
Common pitfalls
- Running it on unsorted input. The discard step silently throws away valid pairs, and the code returns none for arrays that contain a perfectly good answer.
- Writing lo <= hi instead of lo < hi, which lets an element pair with itself - a[3] + a[3] is not a pair the problem allows.
- Sorting first, then reporting positions in the sorted array when the problem wants indices into the original. Sort (value, index) pairs, or switch to the hash-map approach.
- In count-every-pair variants, forgetting to skip runs of duplicate values, which double-counts pairs or loops forever on arrays like 3, 3, 3, 3.
Where it is used
- Two-sum on sorted input, and 3Sum - which runs this exact loop inside an outer scan.
- Container with most water and trapping rain water, where the shorter side decides which pointer moves.
- Merging two sorted sequences, and intersection or union of sorted lists.
- Palindrome checks - the same converging shape, comparing characters instead of summing values.
Frequently asked questions
What are the time and space complexity of the two pointers technique?
O(n) time in the worst case: lo only rises and hi only falls, so together they take at most n steps before meeting. Space is O(1) - two indices and a running sum, nothing that grows with the input. The brute-force pair scan it replaces is O(n²).
How do I know when to use two pointers?
Three signs: the data is sorted or can be sorted, the answer involves a pair or a shrinking range, and one comparison can eliminate a whole group of candidates at once. If checking a[lo] + a[hi] tells you nothing certain about the neighbouring pairs, the technique does not apply.
Does two pointers work on an unsorted array?
Not in this converging form. The discard step relies on order: too small must mean no partner for a[lo] exists anywhere. Unsorted, that inference fails. Either sort first - O(n log n), and it scrambles indices - or use a hash set for O(n) time at O(n) space.
What is the difference between two pointers and sliding window?
Here the pointers start at opposite ends and converge, and the answer is a pair. A sliding window's two pointers move in the same direction, and the answer is the stretch between them. Both are linear for the same reason: no pointer ever moves backwards.