</>EmbeddedInterview

How do you solve Two Sum (find two numbers that add up to a target)?

EasyArrays & Strings (Coding Round)

Short answer: For an unsorted array, the brute-force check of every pair is O(n²). If the array is sorted (or you can sort a copy with indices), use two pointers from both ends: if the sum is too small move the left pointer up, if too large move the right pointer down, O(n). With a hash table of values already seen, it is O(n) on unsorted input.

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

/* sorted input: two pointers, O(n) time, O(1) space */
bool two_sum_sorted(const int *a, size_t n, int target, size_t *i_out, size_t *j_out)
{
    if (n < 2) return false;
    size_t i = 0, j = n - 1;
    while (i < j) {
        long sum = (long)a[i] + a[j];          /* avoid int overflow */
        if (sum == target) { *i_out = i; *j_out = j; return true; }
        if (sum < target) i++;
        else              j--;
    }
    return false;
}
/* {1, 3, 4, 6, 9}, target 10 -> indices 0 and 4 (1 + 9) */

Why moving the pointers is safe: if a[i] + a[j] is too small, a[i] cannot pair with any element left of j either (they are all ≤ a[j]), so i can be discarded. The symmetric argument discards j when the sum is too big.

Unsorted input options

Method Time Extra memory Embedded suitability
Nested loops O(n²) O(1) fine for n < ~100
Sort a copy of (value, index) pairs + two pointers O(n log n) O(n) good, deterministic
Hash set of seen values O(n) average O(n) needs a hash table; avoid dynamic allocation on MCUs
Lookup table (small value range, e.g. 0..255) O(n) O(range) excellent when values are small

Watch for: using the same element twice (target 8 with a single 4), duplicate values, and overflow when adding two large ints.

Follow-ups: count all pairs, closest sum to the target (track the minimum |sum − target| while moving the pointers), and 3Sum (fix one element, run two pointers on the rest: O(n²)).