Two Pointers

The Two-pointers technique can be used to solve problems that involve arrays, linked lists, or other sequences.

These sequences are not necessarily ordered, but, if so, you might need additional data structures to keep track of some information.

A Classic Example

Let's take Two Sum II - Input Array Is Sorted as a classic example for a Two-pointers algorithm.

We surely need to take advantage of the fact that the array is ordered¹. If so, we can easily establish if the target cannot fit in the input. Suppose a target of 10, with a list like [1, 2, 3, 4, 5].

Since the list is already ordered, we know that the elements at the positions i-1 and i-2 (last and second to last, respectively) are the two highest values of the list (5 and 4 in our case). The sum of the two values will not reach the target (9 < 10), which means that no other sum between any two other values in the list can reach the target.

In fact, if the sum of the two highest values is less than the target, how can we find two other values big enough to reach the target? Well, we cannot since the list is ordered.

Then, how can we use such information?

Suppose that we start one pointer from the left and one from the right and we sum their values. We will end up by summing up the minimum (element pointed by the left pointer) and maximum (element pointed by the right pointer), having three possibilities:

1. nums[left] + nums[right] == target: we found the target, there's nothing else to do.
2. nums[left] + nums[right] < target: the number we found is too small. So, summing up the current minimum and maximum is not enough. What can we do? Logically, we can simply find a new minimum and try with it, since the previous one was too small. We still need the current maximum as it is fundamental to find a target.
3. nums[left] + nums[right] > target, which means that the number that we found is too big. In this case, the sum between the minimum and maximum is too big, so we can do the opposite: discard the current maximum by trying with a new one, and keep the current minimum.

The implementation would look something like:

from typing import List


class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1

        while left < right:
            pointers_sum = numbers[left] + numbers[right]
            if pointers_sum == target:
                return [left + 1, right + 1]

            if pointers_sum < target:
                left += 1
            else:
                right -= 1

        assert False, "Unreachable. Expected a single solution for the input."

Which has the following complexity:

• Time: $O(n)$
• Space: $O(1)$

Where n is the size of the list numbers.