practice · easy · from Arrays

Two Sum

time: O(n)
space: O(n)
tags: arrays · hash-tables

in the wild Sensor calibration — pair up two readings whose sum matches a known reference.

Problem

Given an array of integers nums and a target t, return the indices of two distinct elements whose values sum to t. If no such pair exists, return None.

Examples

nums = [2, 7, 11, 15], t = 9 → Some((0, 1)) — because 2 + 7 = 9
nums = [3, 3], t = 6 → Some((0, 1))
nums = [1, 2, 3], t = 100 → None

Why this is the canonical hash-table problem

The naïve solution scans every pair — O(n²). The whole speedup comes from changing the question we ask:

Naïve: "for each pair (i, j), does nums[i] + nums[j] == t?"
Better: "for each i, does the complement t - nums[i] already exist somewhere I've seen?"

The second framing turns the inner scan into a membership query. A hash table answers membership queries in O(1) average. We trade O(n) extra memory for O(n) time — and that's the trade you make every time you "remember what you've seen."

Hints

Hint 1 — the brute force

Two nested loops over nums is O(n²). Can you eliminate the inner loop?

Hint 2 — what to remember

For each element nums[i], what value would nums[j] need to be? Could you check for that value in O(1) if you'd remembered every previous element along with its index?

Hint 3 — pseudocode

seen = {}            # value → index
for i, n in enumerate(nums):
    if (t - n) in seen:
        return (seen[t - n], i)
    seen[n] = i
return None

You don't need to insert n before the lookup — that would let nums[i] pair with itself.

Solution

def two_sum(nums: list[int], t: int) -> tuple[int, int] | None:
    seen: dict[int, int] = {}   # value -> index
    for i, n in enumerate(nums):
        if (t - n) in seen:
            return (seen[t - n], i)
        seen[n] = i
    return None

# Test cases — printing so the runner panel shows results.
cases = [
    ([2, 7, 11, 15], 9,   (0, 1)),
    ([3, 3],         6,   (0, 1)),
    ([1, 2, 3],      100, None),
    ([4],            8,   None),   # don't pair with self
]
for nums, t, expected in cases:
    got = two_sum(nums, t)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} two_sum({nums}, {t}) = {got}")

function twoSum(nums, t) {
  const seen = new Map();         // value -> index
  for (let i = 0; i < nums.length; i++) {
    const complement = t - nums[i];
    if (seen.has(complement)) return [seen.get(complement), i];
    seen.set(nums[i], i);
  }
  return null;
}

// Test cases — console.log so the runner panel shows results.
const cases = [
  [[2, 7, 11, 15], 9,   [0, 1]],
  [[3, 3],         6,   [0, 1]],
  [[1, 2, 3],      100, null  ],
  [[4],            8,   null  ],   // don't pair with self
];
for (const [nums, t, expected] of cases) {
  const got = twoSum(nums, t);
  const ok  = JSON.stringify(got) === JSON.stringify(expected);
  console.log(`${ok ? "✓" : "✗"} twoSum(${JSON.stringify(nums)}, ${t}) = ${JSON.stringify(got)}`);
}

use std::collections::HashMap;

pub fn two_sum(nums: &[i32], t: i32) -> Option<(usize, usize)> {
    let mut seen: HashMap<i32, usize> = HashMap::new();
    for (i, &n) in nums.iter().enumerate() {
        if let Some(&j) = seen.get(&(t - n)) {
            return Some((j, i));
        }
        seen.insert(n, i);
    }
    None
}

fn main() {
    // Each case: (nums, target, expected)
    let cases: &[(&[i32], i32, Option<(usize, usize)>)] = &[
        (&[2, 7, 11, 15], 9,   Some((0, 1))),
        (&[3, 3],         6,   Some((0, 1))),
        (&[1, 2, 3],      100, None),
        (&[4],            8,   None),     // don't pair with self
    ];
    for (nums, t, expected) in cases {
        let got = two_sum(nums, *t);
        let mark = if got == *expected { "✓" } else { "✗" };
        println!("{mark} two_sum({:?}, {}) = {:?}", nums, t, got);
    }
}

#include <unordered_map>
#include <optional>
#include <utility>
#include <vector>
#include <iostream>

std::optional<std::pair<int, int>>
two_sum(const std::vector<int>& nums, int t) {
    std::unordered_map<int, int> seen;   // value -> index
    for (int i = 0; i < (int)nums.size(); ++i) {
        int complement = t - nums[i];
        auto it = seen.find(complement);
        if (it != seen.end()) return std::make_pair(it->second, i);
        seen[nums[i]] = i;
    }
    return std::nullopt;
}

int main() {
    auto show = [](const std::vector<int>& v, int t) {
        auto r = two_sum(v, t);
        std::cout << "two_sum(.., " << t << ") = ";
        if (r) std::cout << "(" << r->first << ", " << r->second << ")\n";
        else   std::cout << "no pair\n";
    };
    show({2, 7, 11, 15}, 9);    // expect (0, 1)
    show({3, 3},         6);    // expect (0, 1)
    show({1, 2, 3},      100);  // expect "no pair"
    show({4},            8);    // expect "no pair" — don't pair with self
    return 0;
}

// C has no stdlib hash table — we roll one with linear probing.
// This is what every "use a hash map" line in higher-level languages
// is doing under the hood.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct { int key; int idx; bool used; } Slot;

bool two_sum(const int* nums, int n, int t, int* out_i, int* out_j) {
    int cap = 2 * n + 16;             // load factor < 0.5
    Slot* table = calloc(cap, sizeof(Slot));
    if (!table) return false;
    bool found = false;

    for (int i = 0; i < n; i++) {
        int complement = t - nums[i];
        // probe for complement
        size_t h = ((unsigned)complement * 2654435761u) % cap;
        while (table[h].used) {
            if (table[h].key == complement) {
                *out_i = table[h].idx; *out_j = i;
                found = true; goto done;
            }
            h = (h + 1) % cap;
        }
        // insert nums[i]
        h = ((unsigned)nums[i] * 2654435761u) % cap;
        while (table[h].used) h = (h + 1) % cap;
        table[h].key = nums[i]; table[h].idx = i; table[h].used = true;
    }
done:
    free(table);
    return found;
}

static void show(const int* nums, int n, int t) {
    int i = -1, j = -1;
    if (two_sum(nums, n, t, &i, &j)) printf("two_sum(.., %d) = (%d, %d)\n", t, i, j);
    else                              printf("two_sum(.., %d) = no pair\n", t);
}

int main(void) {
    int a[] = {2, 7, 11, 15}; show(a, 4, 9);    // expect (0, 1)
    int b[] = {3, 3};         show(b, 2, 6);    // expect (0, 1)
    int c[] = {1, 2, 3};      show(c, 3, 100);  // expect "no pair"
    int d[] = {4};            show(d, 1, 8);    // expect "no pair" — don't pair with self
    return 0;
}

idle

The crucial detail across all four languages: we check the hash table before inserting n. If we inserted first, the entry for n itself could match the complement query — that's the "pair with self" bug.

Complexity

Time: O(n) — one pass over the array. Each step does a constant-time hash lookup + insert.
Space: O(n) — the hash table can grow to hold every element before a match is found.
Tradeoff: Brute force is O(n²) time + O(1) space. Two Sum is the canonical example of trading memory for time.

In the wild

Anytime you'd otherwise scan-pair, a hash of "what I've already seen" replaces the inner loop. Patterns this shape powers:

Sensor fusion: "given a new IMU reading, find the most recent matching odometry tick within tolerance" → hash keyed by quantized timestamp.
Frequency counting: "is there a duplicate?" → hash with bool value; insert and return true on second occurrence.
Schema joining: an in-memory equi-join between two tables is a one-pass Two Sum across rows.

Variations to think about

Three Sum. nums[i] + nums[j] + nums[k] == 0. Sort, then for each i run two-pointer over the rest. O(n²) — beats the obvious O(n³) because the sorted array enables the two-pointer move.
Two Sum on a sorted array. Use two pointers from each end — O(n) time, O(1) space. Sorting is the wedge that buys the constant-space solution.
Two Sum return count of pairs. Same hash approach but you keep counts, not first-seen indices.