Know this before you start: “Opposite ends: left and right meeting in the middle”
Two pointers from opposite ends
Start one index at each end and move them toward each other. Each step rules something out for good, so one pass is enough.
The idea
Put LEFT at index 0 and RIGHT at the last index. Look at both, decide which one can be thrown away, move that pointer inward, and repeat until they meet.
It works when looking at the two ends tells you which side is useless: in a sorted array, a sum that's too small means the left value is too small; in a palindrome check, the two ends must match.
Every step moves a pointer, so the whole thing is O(n) with O(1) extra space.
See it step by step
Is “racecar” a palindrome?
- L = r, R = r → match, move both inward
- L = a, R = a → match; L = c, R = c → match
- L and R meet at 'e' → every pair matched: palindrome.
In code (Python)
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def pair_with_sum(sorted_nums, target):
left, right = 0, len(sorted_nums) - 1
while left < right:
total = sorted_nums[left] + sorted_nums[right]
if total == target:
return left, right
if total < target:
left += 1 # need bigger: move the small end
else:
right -= 1 # need smaller: move the big end
return None
print(is_palindrome("racecar")) # True
print(pair_with_sum([1, 3, 4, 6, 9], 10)) # (0, 4)O(n) time, O(1) space.
When you'll use it
- Palindromes, reversing in place, pairs or triples with a target sum in sorted data, container-with-most-water style problems.
Common mistakes
- `left <= right` when an element mustn't pair with itself.
- Using it on unsorted data where the ends don't tell you which way to go.
