Introduction to Two Pointers Pattern

Each step removes at least one number from consideration, and no number is visited twice. That gives O(N) time, against O(N²) for the nested loops. The pointers are two integers, so the extra space is O(1).

Recognize it when

Use Two Pointers when the question shows these signs.

• The input is sorted, or you are allowed to sort it first.
• You are asked for a pair, a triplet, or a subarray that meets a condition. Common conditions are a target sum, a comparison, or a duplicate rule.
• The question says "in place" or "using constant extra space".
• Your first idea is two nested loops over the same array. This is the most reliable signal of the five. When you notice it, stop and ask whether moving one pointer could replace the inner loop.
• You are comparing two sequences against each other, one pointer in each.

It is not this pattern when:

• The array is unsorted and the question needs the original indices. Sorting destroys them.
• You need a contiguous window whose size or contents change as you scan. That is Sliding Window.
• The data is a linked list and the question asks about a cycle or a midpoint. That is Fast and Slow Pointers.

The template

Almost every problem in this chapter is a variation on this skeleton.

function findPair(array, target):
    left  = 0
    right = length(array) - 1

    while left < right:
        sum = array[left] + array[right]

        if sum == target:
            return [left, right]      # the condition is met
        if sum < target:
            left = left + 1           # need a larger value
        else:
            right = right - 1         # need a smaller value

    return []                         # the pointers met, nothing found

The skeleton has three decisions. while left < right is the stopping rule. The comparison in the middle is the test. The two moves decide what gets discarded.

For a different problem you change the comparison and change what gets returned. The skeleton stays the same.

Variants in this chapter

The same two pointers move in several different ways. These are the shapes used in this chapter.

Learn the converging variant first. The other four are easier to follow once it is familiar.

Watch out for

• Forgetting to skip duplicates. In the triplet problems the same answer will be produced several times unless you advance past repeated values after a match.
• Using the wrong stopping condition. left < right stops before a number is paired with itself. left <= right allows it. Which one you need depends on the question, so decide it deliberately.
• Sorting when you must report original indices. Sort a copy that keeps each value paired with its original index, or use a hash map instead.
• Moving both pointers after a comparison that failed. Only the side that can improve the result should move, otherwise you can skip past the answer.
• Assuming sorted input. If the question does not promise it, sorting costs O(N log N) and that becomes the real complexity of your solution.

How this compares with nearby patterns

Sliding Window is the pattern most often confused with this one, and it is the same idea under a different rule. There, both pointers move in one direction and the region between them is the answer. Here they move toward each other and the region between them is what is left to search.

Key Takeaways

• Two Pointers replaces a nested loop with a single pass, taking O(N²) down to O(N).
• It works because sorted order tells you which pointer to move.
• Every move must discard values that cannot be part of any answer. If a move cannot justify that, the pattern does not apply.
• The skeleton is fixed. The comparison and the return value are what change between problems.
• Extra space stays O(1), which is often the reason this pattern is the expected answer.

Let's apply it to the first problem, Pair with Target Sum.