The Two Pointers Pattern
Two pointers are two positions in a list that move during a search. The positions usually start at opposite ends of the list.
The recognition signal
The signal is a list in order with a question about a pair.
signals = ["List is in order", "Question asks for a pair", "Pair must add to a target"]
for signal in signals:
print("Signal " + signal)The template
The template moves one pointer based on the current sum.
def find_pair(numbers, target):
left = 0
right = len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return True
if total < target:
left = left + 1
else:
right = right - 1
return False
print(find_pair([1, 2, 4, 7], 9))
print(find_pair([1, 2, 4, 7], 20))Worked problem reversing a list
Reversing a list swaps values from both ends inward.
values = [1, 2, 3, 4, 5]
print("Before " + str(values))
left = 0
right = len(values) - 1
while left < right:
temp = values[left]
values[left] = values[right]
values[right] = temp
left = left + 1
right = right - 1
print("After " + str(values))Example
def is_palindrome(word):
left = 0
right = len(word) - 1
while left < right:
if word[left] != word[right]:
return False
left = left + 1
right = right - 1
return True
print(is_palindrome("racecar"))
print(is_palindrome("hello"))Key points
- Two pointers start at the first and last positions.
- Each pointer moves one step at a time.
- A pointer moves when its value cannot be part of the answer.
- The search stops when the pointers meet or cross.
- Two pointers fit a list that is in order.
- Two pointers are simply two positions tracked together.
The program checks a word from both ends inward. It returns false at the first pair that differs. A word with no differing pair is a palindrome.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
A list is in order and the question asks for a pair that adds to a target. Which approach fits best?