Two pointers
Track two positions in an array or string and move them according to a rule. The pointers can move toward each other or in the same direction, often avoiding a nested loop.
Problems this pattern can solve
- Pair sum in a sorted array
- Check whether a string is a palindrome
- Remove duplicates from a sorted array in place
- Merge two sorted arrays
Task: pair sum
Given an ascending sorted integer array and a target, return True if two values at different indices add up to the target. Otherwise, return False.
Duplicates and negative numbers are allowed. You cannot reuse one element. Fewer than two elements means False.
nums = [1, 2, 4, 6, 7], target = 9
True: 2 + 7 = 9
Two-pointer video example
nums = [1, 2, 4, 6, 9], target = 8
True: 2 + 6 = 8
Brute force: check every pair.
Fix i, then move j through the later indices. Starting at i + 1 avoids duplicate pairs and using an element twice. Return immediately when a sum matches.
Time · O(n²)
At worst, check (n − 1) + … + 1 = n(n − 1)/2 pairs. A first-pair match takes O(1).
Extra space · O(1)
Only loop indices are stored. No extra array is created.
Checking every pair is inefficient for large arrays. Next, use sorted order to optimize the search with two pointers.
Two pointers: move inward.
Start at both ends of an ascending sorted array. If the sum is too small, move left rightward. If too large, move right leftward. Stop on a match or when the pointers meet.
Why it works: a sum that is too small means even the largest partner cannot make the left value work. A sum that is too large means even the smallest partner cannot make the right value work. Each move safely discards one candidate.
Use an array sorted in ascending order for two pointers.
Sorted scan · O(n) time / O(1) space
Each comparison removes one candidate: at most n − 1 comparisons, using two indices and a sum.
For sorted input, this is optimal: each step moves one pointer inward, reducing the worst-case time from O(n²) to O(n) with O(1) extra space.