What Is the Two Pointers Technique?

Two pointers works when the array is already ordered and a comparison can eliminate a whole region of the search space. If the input is sorted, then knowing the relationship between two values tells you something about every element between them, and you can discard that region permanently instead of testing it. Problems involving sorted arrays, palindromes, or finding a pair with a given sum are the classic cases.

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

print(is_palindrome("racecar"))
print(is_palindrome("python"))

The palindrome check is the purest example. The two pointers walk towards each other from the ends, and a single mismatch disproves the whole claim, so the function returns early. It is O of n time and O of 1 space, and it never allocates a reversed copy of the string, which is how the naive solution usually starts.

What disqualifies a problem is the absence of a monotonic rule. If the array is unsorted, a comparison between two elements tells you nothing about the elements in between, so you cannot discard them and the technique collapses into a quadratic scan. Another disqualifier is when the relationship between the two pointers depends on the whole history rather than on the current values.

The trade-off to mention is that two pointers is a space optimisation of a quadratic search, and it is only available when the data already carries the order you need. If you would have to sort first, the O of n log n sort and the extra copy often cost more than the map-based approach that solves the same problem in linear time with no precondition.

Because the array is sorted, and because every other element paired with the current left element would produce an equally small or smaller sum. If the sum of the left and right values is below the target, then the left value plus any element to its left would be even smaller, and the left value plus any element other than the current right one would also be smaller. So the current left element cannot be part of any valid pair at all, and discarding it loses nothing.

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return left, right
        if total < target:
            left += 1
        else:
            right -= 1
    return None

print(pair_with_sum([1, 2, 4, 6, 9], 10))
print(pair_with_sum([1, 2, 4, 6, 9], 100))

The first call prints the pair zero and four, because one plus nine is exactly ten. The second prints None: the biggest sum available is six plus nine, which is short of a hundred, so both pointers walk towards the middle and the loop terminates without a match.

The mirror argument handles the other branch. If the sum is too large, the right element cannot be part of any valid pair, because pairing it with anything smaller than the current left element, which is the smallest remaining candidate, would only make the sum larger. So the right pointer moves inwards.

That is the general shape of every two pointers argument: each pointer movement must eliminate a candidate that provably cannot appear in any remaining answer. The trade-off to state is that the technique needs the sorted precondition, and the moment you insert a value into the middle of the array the ordering guarantee breaks and you must fall back on a different approach.