Two Sum: Find a Pair in an Array That Sums to a Target

Two Sum: Find a Pair in an Array That Sums to a Target

Two Sum is the most-asked coding interview problem ever. It’s LeetCode #1, the canonical opener at FAANG, AI labs, fintechs, and every hiring funnel that uses standard data-structures-and-algorithms questions. The problem itself is simple — find two indices in an array whose values sum to a target — but interviewers use it to evaluate fluency on time/space trade-offs, hash-map mechanics, and follow-ups that get progressively harder. This guide covers the standard approaches, working code, and the variations that interviewers ask after the basic solution lands.

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Assume exactly one solution exists; you may not use the same element twice.

Examples:

• nums = [2, 7, 11, 15], target = 9 → [0, 1] (2 + 7 = 9)
• nums = [3, 2, 4], target = 6 → [1, 2] (2 + 4 = 6)
• nums = [3, 3], target = 6 → [0, 1]

Approach 1: Brute Force (O(n²))

Check every pair. Useful as the warm-up answer to demonstrate you understood the problem before optimizing.

def two_sum_brute(nums: list[int], target: int) -> list[int]:
    """O(n^2) time, O(1) space."""
    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 []

Complexity: O(n²) time, O(1) space. Acceptable for small inputs, rejected for any non-trivial array size.

Approach 2: Hash Map (Standard Answer, O(n))

For each element, the complement is target - element. If we’ve seen the complement already, return its index and the current index. Otherwise, store the current element with its index.

def two_sum(nums: list[int], target: int) -> list[int]:
    """O(n) time, O(n) space — single pass with hash map."""
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []


# Tests
print(two_sum([2, 7, 11, 15], 9))   # [0, 1]
print(two_sum([3, 2, 4], 6))        # [1, 2]
print(two_sum([3, 3], 6))           # [0, 1]

Complexity: O(n) time average (hash map lookups are O(1) amortized), O(n) space.

This is the answer the interviewer expects. Single pass, clean indexing, handles duplicates correctly because we check seen before adding the current element.

Approach 3: Two Pointers (For Sorted Input)

If the array is already sorted, two pointers from both ends gives O(n) time and O(1) space. The trick is the array must be sorted (or you must accept O(n log n) sorting cost).

def two_sum_sorted(sorted_nums: list[int], target: int) -> list[int]:
    """O(n) time, O(1) space — assumes sorted input."""
    left, right = 0, len(sorted_nums) - 1
    while left < right:
        s = sorted_nums[left] + sorted_nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []

Complexity: O(n) time, O(1) space (vs O(n) for the hash map approach). The catch: you need a sorted array. If the original problem requires returning indices into the unsorted array, you must track original indices through the sort, which complicates the code.

This is LeetCode #167 (Two Sum II — Input Array is Sorted). Different problem; same name family.

Common Variations

Two Sum — return all pairs

What if there are multiple valid pairs and you must return them all? Switch from “return on first match” to “collect all matches.” Be careful about duplicates: [1, 1, 2] with target 3 — does [0, 2] and [1, 2] count as two pairs or one? Clarify with the interviewer.

3Sum (LeetCode #15)

Find all triplets that sum to zero. Standard approach: sort the array, then for each element, use two pointers on the remaining elements to find pairs summing to its negation. O(n²) time, O(1) space (excluding sorting).

def three_sum(nums: list[int]) -> list[list[int]]:
    """O(n^2) time."""
    nums.sort()
    result = []
    n = len(nums)
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # skip duplicate first element
        left, right = i + 1, n - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif s < 0:
                left += 1
            else:
                right -= 1
    return result

4Sum and beyond

Generalize 3Sum recursively. K-sum is O(n^(k-1)) with the standard approach — the time grows exponentially in k.

Two Sum on a stream / data structure design

(LeetCode #170) Implement TwoSum as a class with add(num) and find(value) operations. Trade-off: optimize add or optimize find. Most candidates implement add as O(1) (insert into a hash map of counts) and find as O(n) (iterate and check complements).

class TwoSum:
    def __init__(self):
        self.counts = {}

    def add(self, num: int) -> None:
        self.counts[num] = self.counts.get(num, 0) + 1

    def find(self, value: int) -> bool:
        for num, count in self.counts.items():
            complement = value - num
            if complement == num and count > 1:
                return True
            if complement != num and complement in self.counts:
                return True
        return False

Common Mistakes

• Storing the value in the hash before checking for the complement. If you store first and check second, nums = [3, 3], target = 6 matches the first 3 against itself. Always check complement in seen before seen[num] = i.
• Using a set instead of a dict. Sets don’t preserve indices. The problem asks for indices, not values; you need a dict from value to index.
• Mishandling duplicates in the brute-force version. The inner loop must start at i + 1, not i, to avoid pairing an element with itself.
• Sorting and forgetting original indices. If the problem requires indices into the unsorted array, sorting destroys the information unless you track it. Pair each element with its original index, sort by value, and return paired indices.
• Not handling the no-solution case. The problem statement may guarantee a solution exists; in real code, return an empty array or raise an exception when nothing matches.

Frequently Asked Questions

See also: Missing or Duplicate Number in an Array • Right Rotate an Array by K Elements • Longest Palindromic Substring

function twoSum(nums, target) {
    const map = new Map();  // value -> index

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (map.has(complement)) {
            return [map.get(complement), i];
        }

        map.set(nums[i], i);
    }

    return [];  // No solution found
}

// Tests
console.log(twoSum([2, 7, 11, 15], 9));  // [0, 1]
console.log(twoSum([3, 2, 4], 6));  // [1, 2]
console.log(twoSum([3, 3], 6));  // [0, 1]
console.log(twoSum([1, 2, 3], 10));  // [] (no solution)

i=0: nums[0] = 2
  complement = 9 - 2 = 7
  map.has(7)? No
  map.set(2, 0) → map = {2: 0}

i=1: nums[1] = 7
  complement = 9 - 7 = 2
  map.has(2)? Yes! map.get(2) = 0
  return [0, 1] ✓

function twoSumSorted(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        const sum = nums[left] + nums[right];

        if (sum === target) {
            return [left, right];
        } else if (sum < target) {
            left++;  // Need larger sum
        } else {
            right--;  // Need smaller sum
        }
    }

    return [];
}

// Test (array must be sorted!)
console.log(twoSumSorted([2, 7, 11, 15], 9));  // [0, 1]
console.log(twoSumSorted([2, 3, 4], 6));  // [0, 2]

function twoSumAllPairs(nums, target) {
    const map = new Map();
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (map.has(complement)) {
            // Add all previous indices that match
            for (const index of map.get(complement)) {
                result.push([index, i]);
            }
        }

        // Store index in array (handle duplicates)
        if (!map.has(nums[i])) {
            map.set(nums[i], []);
        }
        map.get(nums[i]).push(i);
    }

    return result;
}

// Test
console.log(twoSumAllPairs([1, 1, 1, 1], 2));
// [[0,1], [0,2], [0,3], [1,2], [1,3], [2,3]]