Introduction to Two Pointers Pattern

Let N be the number of values in the array.

At each step, at least one pointer moves. A pointer can move across the array only once. Therefore, the time complexity is O(N).

The algorithm stores only two indices and the current sum. Its extra space complexity is O(1).

The improvement is important:

• Checking every pair takes O(N²) time.
• Two Pointers takes O(N) time for this sorted pair-sum problem.

Recognize it when

Two Pointers may be useful when you see these signs:

• The input is sorted, or you are allowed to sort it.
• The problem asks for a pair or triplet that meets a condition.
• The problem asks you to change an array in place.
• The problem asks you to use constant extra space.
• Your first solution uses two nested loops over the same array.
• You are comparing two arrays or strings, with one position in each input.

The most useful signal is the nested loop. Ask this question: "Can one pointer replace the inner loop?"

Do not use this basic pattern when:

• The array is unsorted and you must return the original indices. A hash map may be better.
• You need a contiguous part of an array or string that grows and shrinks. Use Sliding Window.
• You need to find a cycle or midpoint in a linked list. Use Fast and Slow Pointers.
• You need to find one specific value in a sorted array. Use Modified Binary Search.

The template

This is the basic template for two pointers that move toward each other:

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

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

        if sum == target:
            return [left, right]

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

    return []

Three parts may change in another problem:

1. The condition that you test.
2. The rule that moves each pointer.
3. The value that you return.

The loop structure often stays the same.

The condition left < right also matters. It stops one array value from being paired with itself.

Variants in this chapter

Two pointers do not always start at opposite ends. They can move in several ways.

Start with the converging variant. It makes the main idea easiest to see.

Watch out for

• Moving the wrong pointer. Move the pointer that can bring the result closer to the target.
• Moving both pointers after a failed comparison. You may skip the correct answer.
• Using the wrong stopping condition. Use left < right when one value cannot be used twice.
• Forgetting duplicate values. Skip repeated values when a problem requires unique pairs or triplets.
• Sorting without checking the output requirement. Sorting changes the original indices.
• Ignoring the cost of sorting. Sorting an unsorted array takes O(N log N) time.

How this compares with nearby patterns

Two Pointers and Sliding Window both use two indices. The difference is what the indices represent.

With Two Pointers, the indices usually show values that we are comparing. With Sliding Window, the indices show the boundaries of one contiguous range.

Key takeaways

• A pointer is an index that shows a position in an array or string.
• Two Pointers processes two positions at the same time.
• Sorted order often tells you which pointer to move.
• Each move must safely remove values that cannot be part of the answer.
• The pair-sum example improves from O(N²) time to O(N) time.
• The basic pair-sum solution uses O(1) extra space.

Now apply this pattern to Pair with Target Sum.