When can you use the two pointers technique, and what makes a problem a good candidate for it?
You use it when the data is sorted, or when you can move a pointer based on a comparison and be sure that you are not going to need it again.
The technique is simple. You keep two indexes in the list, usually one at each end, and you move them inwards based on what you find.
def is_palindrome(text):
left, right = 0, len(text) - 1
while left < right:
if text[left] != text[right]:
return False
left += 1
right -= 1
return True
So what makes a problem a good candidate? Two things.
The first one is that the data is sorted, or that it has some order that lets a comparison tell you which way to move. The palindrome check does not need the data to be sorted, because it compares two ends and moves both inwards.
The second one is that you can throw something away. When you move a pointer inwards, you have to be sure that whatever you passed over cannot take part in the answer. That is the rule that makes the technique safe, and it is why the sorted pair with sum works and a lot of other problems do not.
So the classic problems for it are the palindrome check, the pair with a given sum, removing the duplicates from a sorted list, and partitioning a list around a pivot.
The next question in this topic explains the safety rule in detail, because it is the part that people get wrong.