Data Structures · Array

Two Sum (Sorted)

The idea

Two shoppers stand at opposite ends of a price-sorted shelf with a fixed budget for exactly two items. If their current pair costs too much, the shopper at the expensive end steps toward cheaper items. Too little? The cheap-end shopper steps up. They close in until the pair fits the budget exactly — or they meet empty-handed.

The problem

Given a SORTED array and a target value, find two elements that add up exactly to the target. The sorted order is the whole trick: one pointer starts at the cheapest value, one at the priciest. Each comparison of their sum against the target tells you with certainty which pointer to move — no guessing, no going back.

Why it's slow

Each step eliminates one element forever, so the walk finishes in at most n-1 comparisons — a single pass. Compare that with the brute force: trying every pair costs n(n-1)/2 checks. The interview follow-up is the unsorted version, where a hash map replaces the sorted order and buys the same single pass for O(n) extra space.

Pseudocode

  1. put one pointer at each end of the sorted array
    Explain this line

    The smallest and largest candidates form the first pair — the extremes bracket every possible sum.

  2. while the pointers have not met
    Explain this line

    Once the pointers meet, every element was considered in some pair; nothing is left to try.

  3. add the two values and compare with the target
    Explain this line

    One sum, one comparison against the target — this decides everything about the next move.

  4. if the sum equals the target — found the pair
    Explain this line

    Exact match: the two pointed-at values are the answer.

  5. if the sum is too big, move the right pointer left
    Explain this line

    Sum too big: the ONLY way down is dropping the largest value — the right pointer's current element can never pair with anything (all partners to its left are even smaller than the current failing pair... larger sums were already ruled out).

  6. otherwise move the left pointer right
    Explain this line

    Sum too small: the smallest value cannot pair with anything — even the largest remaining partner was not enough. Retire it.

  7. the pointers met — no pair sums to the target
    Explain this line

    Every element was eliminated with proof — the target sum is impossible in this array.

Complexity

Best Average Worst Space
O(1) O(n) O(n) O(1)

Each comparison permanently eliminates one element, so at most n-1 steps. Brute force checks all n(n-1)/2 pairs; sorted order makes every elimination provably safe.

Code

python 
def two_sum_sorted(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return (lo, hi)
        if s > target:
            hi -= 1
        else:
            lo += 1
    return None
java 
static int[] twoSumSorted(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int s = a[lo] + a[hi];
        if (s == target) return new int[] {lo, hi};
        if (s > target) hi--; else lo++;
    }
    return null;
}
cpp 
std::optional<std::pair<int,int>> twoSumSorted(const std::vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo < hi) {
        int s = a[lo] + a[hi];
        if (s == target) return {{lo, hi}};
        if (s > target) --hi; else ++lo;
    }
    return std::nullopt;
}
javascript 
function twoSumSorted(a, target) {
  let lo = 0, hi = a.length - 1;
  while (lo < hi) {
    const s = a[lo] + a[hi];
    if (s === target) return [lo, hi];
    if (s > target) hi--; else lo++;
  }
  return null;
}
dart 
List<int>? twoSumSorted(List<int> a, int target) {
  var lo = 0, hi = a.length - 1;
  while (lo < hi) {
    final s = a[lo] + a[hi];
    if (s == target) return [lo, hi];
    if (s > target) {
      hi--;
    } else {
      lo++;
    }
  }
  return null;
}

Quick check