</>EmbeddedInterview
← All problems · Arrays & Searching

Two Sum in a Sorted Array (Two Pointers)

Easy

Given an array sorted in ascending order and a target, find two different elements whose sum equals target.

Implement bool two_sum_sorted(const int *a, size_t n, int target, size_t *i, size_t *j). On success write the two indexes (*i < *j) and return true; return false if no pair exists. Use O(1) extra memory and a single pass.

Example: {1, 2, 3, 4, 5, 6}, target 8 → indexes 1 and 5 (values 2 + 6). Any valid pair is accepted.

Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.

Start one pointer at each end. If the sum is too small, the only way to grow it is to move the left pointer right; if it is too large, move the right pointer left.

#include <stdio.h>
#include <stdbool.h>
#include <stddef.h>

bool two_sum_sorted(const int *a, size_t n, int target, size_t *i, size_t *j)
{
    if (n < 2) return false;
    size_t left = 0, right = n - 1;

    while (left < right) {
        long sum = (long)a[left] + a[right];   /* avoid int overflow */
        if (sum == target) {
            *i = left;
            *j = right;
            return true;
        }
        if (sum < target)
            left++;            /* need a bigger sum */
        else
            right--;           /* need a smaller sum */
    }
    return false;
}

Because the array is sorted, each comparison throws away one candidate for good:

  • If a[left] + a[right] < target, then a[left] plus any element is too small (a[right] is already the largest left), so left can never be part of the answer.
  • If the sum is too large, a[right] plus any element is too large, so drop right.

Each step moves one pointer, so it is O(n) time, O(1) memory, versus O(n²) for checking every pair.

Walk-through: {1, 2, 3, 4, 5, 6}, target 8

left right a[left] + a[right] action
0 5 1 + 6 = 7 too small → left++
1 5 2 + 6 = 8 found

Edge cases interviewers check: fewer than 2 elements; no pair; the same element must not be used twice (left < right guarantees that); duplicates (3 + 3); negative numbers; overflow of a[left] + a[right] for large values, which is why the sum is computed as long.

Follow-ups: for an unsorted array, use a hash set for O(n) time and O(n) memory, or sort first for O(n log n). The same two-pointer idea solves three-sum (fix one element, two-pointer the rest) and "pair with the closest sum".

solution.c
OutputPress Run to compile and test your code.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
static int ok(const int *a, size_t n, int t)
{
    size_t i = 99, j = 99;
    if (!two_sum_sorted(a, n, t, &i, &j)) return 0;
    return i < j && j < n && a[i] + a[j] == t;
}
int main(void)
{
    const int a[] = { 1, 2, 3, 4, 5, 6 };
    CHECK(ok(a, 6, 8));
    CHECK(ok(a, 6, 3));                       /* 1 + 2 */
    CHECK(ok(a, 6, 11));                      /* 5 + 6 */
    size_t i, j;
    CHECK(!two_sum_sorted(a, 6, 100, &i, &j));
    CHECK(!two_sum_sorted(a, 6, 2, &i, &j));  /* 1 + 1 not allowed: same element */
    const int d[] = { -5, -1, 0, 3, 3, 9 };
    CHECK(ok(d, 6, 6));                       /* 3 + 3, two different elements */
    CHECK(ok(d, 6, -6));
    CHECK(!two_sum_sorted(a, 0, 0, &i, &j));
    CHECK(!two_sum_sorted(a, 1, 2, &i, &j));
    puts(fails ? "Some tests failed" : "All tests passed");
    return fails != 0;
}