Two Pointers
One from each end.
Many array problems have a beautiful trick. Keep two positions, called pointers. Often one starts at the beginning and one at the end, and they walk towards each other. It turns slow nested loops into one fast pass.

- Keep two positions
- One at each end
- Walk towards each other
Pair with a target sum
Here's a classic. In a sorted list, find two numbers that add up to a target. Left starts at the beginning, and right at the end. If the pair is too small, move left up, to a bigger number. If it's too big, move right down. Run it. Three and eleven make fourteen, and we only walked through the list once. That's O of N, instead of O of N squared.
def pair_sum(nums, target):
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return nums[left], nums[right]
if total < target:
left += 1
else:
right -= 1
return None
print(pair_sum([1, 3, 4, 6, 8, 11], 14))(3, 11)
When to use two pointers
Reach for two pointers when the data is sorted, or when you're comparing things from both ends, like in a palindrome. It's also handy for reversing a list in place, merging two sorted lists, and removing duplicates. The clue is usually, sorted data, and pairs.
| key | value |
|---|---|
| Sorted data | pairs with a target |
| Both ends | palindromes |
| In place | reversing |
| Two lists | merging |
Summary
Two pointers walk through an array from both ends, turning O of N squared into O of N. Next, practice. Reversing a list, the two pointer way.
Key takeaways- left and right
- Move one each step
- O(n) instead of O(n²)