Let two positions do the searching.
Use two pointers to narrow a search space without checking every possible pair.
The pointers may begin at opposite ends or move together through a sequence. Each move should discard possibilities while preserving the answer you are looking for.
When does this pattern help?
Two pointers are useful for pairs in a sorted array, comparing characters from both ends, removing duplicates in place, or finding a range that meets a condition. The key is knowing which pointer movement makes sense from the current values.
Start at the beginning and end of a sorted array. Move inward based on whether the current result is too small or too large.
Move a slow pointer to track a position to keep, while a fast pointer scans ahead for useful values.
Find two values that sum to 12
Start at both ends. 1 + 9 = 10, which is below 12. Move the left pointer inward to make the sum larger.
How to choose which pointer moves
- Use the ordering: this example works because the values are sorted.
- Sum too small? Move the left pointer right to increase the sum.
- Sum too large? Move the right pointer left to decrease the sum.
For an unsorted array, this sum rule does not work as-is. Sorting may help, but consider whether sorting changes the question or loses the original indices.
Find a pair in a sorted array
Given the sorted array [1, 3, 4, 6, 8, 10] and target 14, enter any pair of values that adds up to the target. Enter 0 if no pair exists.
numbers = [1, 3, 4, 6, 8, 10]
target = 14Return the pair of values.Show a hint
Begin with 1 and 10. Their sum is 11, so move the left pointer toward larger values.
Two Pointers at work
A shop has sorted item prices [2, 5, 7, 11, 14]. Can you find two items that cost exactly 16 together?
Show one possible approach
Yes: 2 + 14 = 16. Start with the cheapest and most expensive prices; because the total matches, you can stop.