Pointers from Both Ends

The problem

A user types a target amount into your checkout screen and asks, "which two of my gift cards add up to exactly this?" The balances are already sorted, smallest to largest. You need to find a pair that sums to the target — or say confidently that none exists.

It feels like a lookup. But the naive way of finding that pair scales badly, and the sorted order you were handed is a gift you're about to throw away.

A first attempt

Try every pair. For each card, loop over every later card and check the sum.

def two_sum_naive(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return [-1, -1]

Correct, but it examines about n²/2 pairs. With 50,000 cards that's over a billion checks. And it ignores the one fact that makes this easy: the array is sorted. We're paying full price for information we already have.

The insight

Put one pointer at the smallest value and one at the largest, then look at their sum:

• If the sum is too small, the only way to grow it is to give up the smallest number — move the left pointer right.
• If the sum is too big, the only way to shrink it is to give up the largest number — move the right pointer left.
• If it's exactly right, you're done.

Every move throws away exactly one number that can never be part of the answer, so the two pointers march toward each other and meet in a single pass.

How it works

target = 9
[1, 2, 4, 7, 11, 15]
 lo              hi     1+15=16 > 9  → hi--
 lo          hi        1+11=12 > 9  → hi--
 lo       hi           1+7 =8  < 9  → lo++
    lo    hi           2+7 =9  ✓

The code

def two_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return [lo, hi]
        if s < target:
            lo += 1
        else:
            hi -= 1
    return [-1, -1]

function twoSumSorted(nums: number[], target: number): number[] {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo < hi) {
    const s = nums[lo] + nums[hi];
    if (s === target) return [lo, hi];
    if (s < target) lo++;
    else hi--;
  }
  return [-1, -1];
}

class Solution {
    public int[] twoSumSorted(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int s = nums[lo] + nums[hi];
            if (s == target) return new int[] {lo, hi};
            if (s < target) lo++;
            else hi--;
        }
        return new int[] {-1, -1};
    }
}

// Caller frees the returned array of length 2.
int* twoSumSorted(int* nums, int numsSize, int target) {
    int* res = malloc(2 * sizeof(int));
    int lo = 0, hi = numsSize - 1;
    res[0] = -1; res[1] = -1;
    while (lo < hi) {
        int s = nums[lo] + nums[hi];
        if (s == target) { res[0] = lo; res[1] = hi; return res; }
        if (s < target) lo++;
        else hi--;
    }
    return res;
}

#include <vector>
using namespace std;

vector<int> twoSumSorted(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo < hi) {
        int s = nums[lo] + nums[hi];
        if (s == target) return {lo, hi};
        if (s < target) lo++;
        else hi--;
    }
    return {-1, -1};
}

Complexity

Each iteration moves exactly one pointer inward, so the pointers can meet after at most n steps — linear time, and no extra memory at all.

When to use it

Practice

Recap

• Two pointers starting at opposite ends exploit sorted (or symmetric) data to solve pair and boundary problems in one linear pass.
• Each comparison lets you safely discard one endpoint, which is why O(n²) brute force collapses to O(n) with O(1) space.
• The pattern generalizes far past pair-sums: palindromes, reversing in place, and max-area problems all ride the same "close in from the edges" idea.