Two pointers
Why it exists
Problem: Given a target sum and an array, find two elements that add up to the target.
Naive approach: Check every possible pair with nested loops, taking O(n^2) time.
Better idea: If the array is sorted, we can put pointers at the ends and move them inward, ruling out O(n) invalid pairs at every step to solve it in O(n) time.
Mental model
Imagine playing a guessing game where you need to hit an exact weight. If you are too heavy, you swap a heavier item for a lighter one. If you are too light, you swap a lighter one for a heavier one.
Two pointers places a 'lo' pointer at the start and a 'hi' pointer at the end of a sorted array. You check their sum against the target. Depending on whether it is too big or too small, you increment 'lo' or decrement 'hi'.
Repeated decision: is the current pair's sum too big (move right in) or too small (move left in)?
Explanation
To use the two pointers technique, your array MUST be sorted. This is the crucial precondition. Without it, you cannot safely eliminate elements.
Here is how you find a pair adding to a target:
1. Sort the array (if not already sorted). This takes O(n log n).
2. Place `lo` at index 0 and `hi` at the last index.
3. Loop while `lo < hi`.
4. Calculate `sum = arr[lo] + arr[hi]`.
5. If `sum == target`, you found it! Return the pair.
6. If `sum < target`, the pair is too small. Since the array is sorted, any pair with `arr[lo]` and an index less than `hi` will be even smaller. Thus, `arr[lo]` can never form a valid pair. Move `lo` right (`lo++`) to increase the sum.
7. If `sum > target`, the pair is too big. Any pair with `arr[hi]` and an index greater than `lo` will be even bigger. Thus, `arr[hi]` can never form a valid pair. Move `hi` left (`hi--`) to decrease the sum.
Why is a move safe? If `arr[lo] + arr[hi]` is too large, no pair using `arr[hi]` can work because every remaining partner is >= `arr[lo]`. So the whole column is discarded -- that is how O(n^2) becomes O(n). The time complexity of the scan is O(n), and the space complexity is O(1). This contrasts with the hash-map approach, which works on unsorted arrays but costs O(n) space.
Let's hand-trace an example with a sorted array: `[1, 2, 3, 4, 7, 9]` and target = 9.
- `lo=0` (value 1), `hi=5` (value 9)
- `sum = 1 + 9 = 10`
- `10 > 9`, so the sum is too big. Move `hi` left: `hi--`
- `lo=0` (value 1), `hi=4` (value 7)
- `sum = 1 + 7 = 8`
- `8 < 9`, so the sum is too small. Move `lo` right: `lo++`
- `lo=1` (value 2), `hi=4` (value 7)
- `sum = 2 + 7 = 9`
- `9 == 9`. Found it: the values 2 and 7 (at indices `lo=1` and `hi=4`) add to the target.
Common mistakes
- Applying two pointers to an unsorted array: Two pointers relies entirely on the sorted property to safely eliminate candidates. If the array is unsorted, you must use a hash map or sort it first.
- Using lo <= hi in the loop condition: A pair requires two distinct elements. If lo == hi, you are using the same element twice. The loop condition must be lo < hi.
Recall questions
- What is the crucial precondition for the two pointers sum technique?
- If the current sum is greater than the target, which pointer moves?
- Why is it safe to discard a pointer when the sum is too large?
- What is the space complexity of the two pointers technique compared to a hash map?
Questions & answers
Given a sorted array of distinct integers and a target value, return the indices of the two numbers such that they add up to target.
Use two pointers, lo at 0 and hi at length - 1. While lo < hi, check the sum. If it equals target, return [lo, hi]. If it is less, increment lo. If it is greater, decrement hi.
Approach: Two pointers inward scan.
Given an array of integers, find if there is a triplet that sums to zero.
Sort the array. Iterate through the array with a loop variable 'i'. For each 'i', use two pointers 'lo = i + 1' and 'hi = length - 1' to find a pair that sums to '-arr[i]'.
Approach: Sort then fix one element and use two pointers for the remaining sum.
Continue learning
Previous: Arrays & Memory
Next: Fast & slow pointers
Next: Sliding window (fixed)
Related: Fast & slow pointers
Related: Two Pointers on Strings