Two Pointer Method

The two pointer method is a key optimization technique for problems on sorted arrays and strings. The variant covered on this page uses two pointers moving toward each other from opposite ends of the input — often called the converging or opposing-ends pattern. By replacing a nested-loop pair search with a single linear pass, it turns many O(n²) brute-force solutions into O(n) with O(1) extra space.

A different two-pointer variant — same-direction pointers that grow and shrink a window over the input, also known as the sliding window pattern — is walked through on the Two-Pointer page. Both share the "two pointer" name but have distinct setups and use cases.

This page demonstrates the converging variant with a walkthrough.

Problem: Pair with target sum (sorted array)

Given a sorted array of integers and a target value, return whether any pair of elements in the array sums to the target.

Example:

>>> has_pair_with_sum([-3, -1, 0, 1, 2, 4], 3)
True

Explanation: the pair (-1, 4) sums to 3, so the function returns True. The pair (1, 2) would also satisfy the condition.

Solution #1: Brute Force

Approach

When an optimal solution isn't immediately clear, it helps to start from any correct one. Here the brute-force approach is to consider every pair (i, j) with i < j and check whether arr[i] + arr[j] equals the target.

Implementation

def has_pair_with_sum(arr, target):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:
                return True
    return False

Time and space complexity

The outer loop runs O(n) times and the inner loop runs up to O(n) times for each i, so the total runtime is O(n²).

The space complexity is O(1) because no auxiliary data structures are allocated.

Notice that the brute force ignores the fact that the input is sorted — every signal the sortedness provides is thrown away.

Improvements

Optimization #1:

Use a hash set to find each complement in constant time

For each element we really only need to ask "does the complement target - element exist elsewhere in the array?" A hash set lets us answer that in O(1) per lookup as we scan once through the list.

def has_pair_with_sum(arr, target):
    seen = set()
    for value in arr:
        if target - value in seen:
            return True
        seen.add(value)
    return False

This brings the time complexity down to O(n), but the hash set adds O(n) auxiliary space — and the algorithm still doesn't exploit sortedness. On a sorted input we can match the O(n) time without the extra space.

Solution #2: Two pointer approach

Approach

Place a left pointer at the start of the array and a right pointer at the end. At each step look at arr[left] + arr[right] and let the sortedness decide which pointer to move:

• If the sum equals the target, return True.
• If the sum is less than the target, the only way to grow it is to move left forward — every element strictly to the left of right is no larger than arr[right], so pairing the current arr[left] with any of them would give an even smaller sum.
• If the sum is greater than the target, the only way to shrink it is to move right backward — by symmetric reasoning, every element strictly to the right of left is no smaller than arr[left], so no pair involving the current arr[right] can shrink the sum further.

Each step rules out exactly one element: either no pair involving the current arr[left] can ever reach the target, or no pair involving the current arr[right] can. Because ruled-out elements are never revisited, the pointers together touch each index at most once.

This continues until either a matching pair is found or the pointers cross, at which point every candidate pair has been considered.

Implementation

def has_pair_with_sum(arr, target):
    left, right = 0, len(arr) - 1

    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return True
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return False

Time and space complexity

The time complexity is O(n) because each iteration advances exactly one pointer and the pointers can move at most n - 1 times in total before they cross.

The space complexity is O(1) because the algorithm only stores the two pointers.

Walkthrough

Take the example of has_pair_with_sum([-3, -1, 0, 1, 2, 4], 3). The pointers start at left = 0 (value -3) and right = 5 (value 4).

• arr[0] + arr[5] = -3 + 4 = 1, which is less than 3. Advance left to 1 (value -1).
• arr[1] + arr[5] = -1 + 4 = 3, which matches the target. Return True.

For contrast, consider has_pair_with_sum([-3, -1, 0, 1, 2, 4], 10):

• -3 + 4 = 1 < 10, advance left to 1.
• -1 + 4 = 3 < 10, advance left to 2.
• 0 + 4 = 4 < 10, advance left to 3.
• 1 + 4 = 5 < 10, advance left to 4.
• 2 + 4 = 6 < 10, advance left to 5.
• Now left == right, so the loop exits and the function returns False.

Why moving a pointer is safe

When arr[left] + arr[right] < target and we advance left, we discard every pair that uses the current arr[left]. That's safe because the largest available partner for arr[left] is arr[right] (the array is sorted and nothing to its right has been seen as smaller), and even that partner doesn't reach the target — every other candidate is ≤ arr[right], so their sums with arr[left] are no larger. By a symmetric argument, decrementing right when the sum is too large only discards pairs that were already too large. This is the loop invariant that makes the linear-pass solution correct: at every step, the optimal pair (if one exists) still lies between the two pointers.

Takeaways

The converging two-pointer pattern thrives whenever the input is sorted — or can be cheaply sorted — and the decision at each step monotonically rules out one direction's worst-case neighbor. Pair-sum on a sorted array, three-sum, container-with-most-water, valid palindrome, reversing a string in place, and "remove from a sorted array" all reduce to this shape.

Note: When the pointers move in the same direction instead of converging — typically advancing one to grow a window and the other to shrink it — the resulting pattern is the sliding window variant. See the Two-Pointer page for that walkthrough.