Solving Sorted-Array Problems with Two Pointers

Sorted order is usable information

Consider the familiar two-sum task:

Given an ascending sorted list of integers and a target, return indices of two distinct elements whose values sum to the target. Return an empty list if no pair exists.

For example:

nums = [-5, -2, 3, 4, 6]
target = 7

The answer is [2, 3] because:

nums[2] + nums[3]  # 3 + 4 = 7

A brute-force solution checks every pair:

def pair_sum_brute_force(nums: list[int], target: int) -> list[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

In the worst case, it checks a quadratic number of pairs, so it takes:

time.

The key word in the prompt is sorted. In an ascending array:

• moving left to the right makes the selected value stay the same or increase;
• moving right to the left makes the selected value stay the same or decrease.

Therefore, if you know whether the current sum is too small or too large, you know which direction can possibly improve it.

The inward two-pointer pattern

Initialize one pointer at each extreme:

left = 0
right = len(nums) - 1

At every step, inspect:

current = nums[left] + nums[right]

There are exactly three cases:

The resulting implementation is short:

def pair_sum_sorted(nums: list[int], target: int) -> list[int]:
    left = 0
    right = len(nums) - 1

    while left < right:
        current = nums[left] + nums[right]

        if current == target:
            return [left, right]
        elif current < target:
            left += 1
        else:
            right -= 1

    return []

The loop condition is deliberately:

while left < right:

It ensures that the two selected elements are at distinct positions. A value may be used twice only when it occurs at two distinct indices:

nums = [1, 1, 4]
target = 2

Here, indices [0, 1] are a valid answer. But one element at index 0 cannot be paired with itself.

The supplied Two Pointers diagram shows the same search process on a larger example. Starting with the smallest and largest values, it moves the pointer that can bring the sum closer to the target and gradually removes impossible candidates.

Trace the algorithm precisely

Use:

nums = [-5, -2, 3, 4, 6]
target = 7

Notice that neither pointer ever moves backward. The search interval only shrinks.

Why a pointer move eliminates an entire set of pairs

In an interview, saying “the array is sorted, so I move a pointer” is not quite enough. The stronger explanation is that each move rules out an entire family of pairs.

When the sum is too small

Suppose:

Because right is currently the largest remaining candidate, every index $k$ between left and right has:

So:

No pair containing the current left value can reach the target. Moving right left would only make the sum smaller, so the only useful move is:

left += 1

When the sum is too large

Now suppose:

Because left is currently the smallest remaining candidate, every index $k$ between left and right has:

Therefore:

No pair containing the current right value can work. Moving left right would only increase the sum, so we must do:

right -= 1

This elimination argument is the reason the approach is correct. It is not a heuristic that happens to work on examples.

A concise interview invariant is:

If a valid pair exists, then before each iteration it lies within the current inclusive interval from left to right.

When the sum is too small, you prove that no solution uses the old left; when it is too large, you prove that no solution uses the old right. Thus, the invariant survives every pointer update.

Complexity and the contrast with hashing

Although the code has a loop and two pointers, it is still linear time.

Each iteration moves exactly one pointer inward. The initial distance between them is at most $n-1$, and that distance decreases by one per unsuccessful iteration. So the algorithm does at most $n-1$ pair comparisons before finding an answer or terminating.

• Time complexity: $O(n)$
• Auxiliary space complexity: $O(1)$

This creates a useful contrast with the previous frequency-counting lesson:

Do not apply the inward pointer rule to an unsorted array. For example, in:

nums = [4, 1, 7, 2]

moving an index right does not reliably increase the value, so “sum too small, move left” has no logical basis.

Sorting an unsorted array can enable two pointers, but it changes the complexity to at least:

It can also destroy the original index information required by many interview prompts. To preserve indices, you would need to sort value-index pairs, which is valid but no longer the simplest default solution.

Common implementation errors

Most two-pointer bugs come from violating the prompt’s assumptions or moving a pointer in the wrong direction.

Moving the wrong pointer

For an ascending array:

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

If the sum is too small and you decrement right, you make the selected right value smaller or equal, so the sum cannot increase. Similarly, incrementing left when the sum is too large cannot help.

Allowing one element to be reused

This is unsafe for a two-sum prompt requiring distinct elements:

while left <= right:

Use:

while left < right:

With left == right, both pointers refer to the same list element.

Returning values when indices were requested

These are different outputs:

return [nums[left], nums[right]]  # values
return [left, right]              # indices

Read the requested return type before coding. The function in this lesson returns zero-based Python indices. Some platforms, including LeetCode 167, ask for one-based positions; in that special case, return:

return [left + 1, right + 1]

Forgetting that negatives and duplicates are valid

The method does not require positive values. It depends only on sorted order. It works for:

pair_sum_sorted([-3, -2, -1], -5)  # [0, 1]
pair_sum_sorted([-1, 2, 3], 2)     # [0, 2]
pair_sum_sorted([1, 1, 1], 2)      # one valid result is [0, 2]

A compact implementation check can use assertions:

assert pair_sum_sorted([], 0) == []
assert pair_sum_sorted([2], 2) == []
assert pair_sum_sorted([2, 3], 5) == [0, 1]
assert pair_sum_sorted([-5, -2, 3, 4, 6], 7) == [2, 3]
assert pair_sum_sorted([1, 1, 1], 2) in ([0, 1], [0, 2], [1, 2])

Two pointers can also move in the same direction

“Two pointers” is a pattern family, not one fixed algorithm. In pair sum, the pointers begin at opposite ends and shrink a search interval. In another common sorted-array problem, one pointer reads every element while the other pointer marks where to write the next kept value.

For example, suppose you must remove duplicates from a sorted list in place and return the number of unique values:

nums = [0, 0, 1, 1, 2, 2, 3]

The desired meaningful prefix becomes:

[0, 1, 2, 3]

A read pointer scans all positions; a write pointer tracks the next free position in the unique prefix.

def remove_duplicates_sorted(nums: list[int]) -> int:
    if not nums:
        return 0

    write = 1

    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1

    return write

The invariant is:

Before processing nums[read], nums[:write] contains exactly the distinct values encountered so far, in sorted order.

The sorted property ensures duplicates are adjacent. Therefore, a value is new precisely when it differs from the last unique value already written.

The pointer movements differ between these problems because the state represented by each pointer differs:

Before choosing pointer updates, first name what each pointer represents.

Key takeaways

For a target-sum problem on an ascending sorted array:

• Start left at index 0 and right at the final index.
• If the sum is too small, increment left; if too large, decrement right.
• Use while left < right to guarantee two distinct elements.
• Each pointer move eliminates an entire set of impossible pairs, which gives both correctness and $O(n)$ time.
• The approach uses $O(1)$ auxiliary space, unlike the hash-map strategy for unsorted two-sum.
• “Two pointers” also includes same-direction read/write patterns, especially for in-place operations on sorted arrays.

Next, you will move from pairs in sorted arrays to sliding windows: a related pointer technique for reasoning about contiguous subarrays and substrings.