Two Pointers

Two pointers use two moving positions to control a search, interval, or pair selection.

The technique often replaces a nested loop with a single pass when movement rules are clear.

Core Idea

The two positions may start at opposite ends and move inward, or both may move from left to right. The key is that each pointer moves in a controlled direction so the total number of moves stays small.

Sorted order often makes the movement rule possible.

Function Contract

has_pair_sum(sorted_values, target) expects sorted_values to be sorted in ascending order.

It returns whether two different positions add to target. The movement rule is valid because sorted order tells which pointer move can still help.

Python Example

def has_pair_sum(sorted_values, target):
    left = 0
    right = len(sorted_values) - 1
 
    while left < right:
        total = sorted_values[left] + sorted_values[right]
        if total == target:
            return True
        if total < target:
            left += 1
        else:
            right -= 1
 
    return False

Because the list is sorted, each move safely discards some pairs.

Step-by-Step Example

For sorted_values = [1, 3, 4, 6, 9] and target = 10, start with left = 0 and right = 4.

1 + 9 = 10, so the pair is found immediately.

For target = 8, 1 + 9 is too large, so right moves left. Then 1 + 6 is too small, so left moves right. The movement rule depends on sorted order.

Why It Works

If the sum is too small, increasing the left pointer is the only useful direction because moving the right pointer left would make the sum even smaller. If the sum is too large, decreasing the right pointer is the useful direction.

This reasoning safely discards many pairs without checking them one by one.

Complexity

Each pointer moves at most n times, so the scan is O(n) after sorting. If sorting is needed first, the total time is usually O(n log n).

Common Confusions

Two pointers is not just “use two variables.” The movement rule must be justified.

If the input is not sorted or does not have a monotonic property, moving one pointer may discard valid answers.

Another common mistake is moving both pointers at the wrong time. Each move should follow from what the current comparison proves.

When To Use It

Use two pointers for sorted pair problems, merging, removing duplicates, partitioning, and interval scans where each pointer can move only forward or inward.

Do not use it when the correct next move cannot be determined from the current state.

The Main Point

Two pointers are valid when pointer movement can be justified. The sorted or monotonic structure is what makes discarding candidates safe.