3  Two Sum

Rank 1 · Pattern: hash-map complement lookup · Target: \(O(n)\) time, \(O(n)\) space

3.1 Problem definition

Given an integer array nums and an integer target, return the indices of two elements whose values add up to target.

3.2 Clarifying questions

1. Should I return the two indices or the two values?
2. May the same array position be used twice? May two different positions contain the same value?
3. Is a valid pair guaranteed, and can more than one valid pair exist?
4. Does the order of the returned indices matter?
5. What input and integer-overflow constraints should I assume?

3.3 Sample answers

1. Return the indices, not the values.
2. The indices must be different, but their values may be equal.
3. Exactly one valid pair exists.
4. Either index order is acceptable.
5. nums is non-null, and the needed arithmetic fits in a signed 32-bit int.

3.4 Data structure: map

The map stores a value and an earlier index with expected constant-time lookup and insertion.

Java

HashMap<Integer,Integer> uses get(x) to retrieve an earlier index and put(value, i) to remember the current one. The map never stores null indices, so a null result means “not found.”

Python

A dict uses needed in index_by_value to test membership, bracket lookup to retrieve an index, and bracket assignment to remember the current one.

Rust

HashMap<i32,usize> uses get(&needed), which returns an Option, and insert(value, index). Iteration order is irrelevant.

3.5 Approach and invariant

The brute-force baseline checks every pair in \(O(n^2)\) time and \(O(1)\) space. The repeated work is searching earlier elements for a complement.

Scan from left to right. At index i, compute needed = target - nums[i]. Look it up once. A successful lookup is necessarily a different, earlier index; otherwise store the current value.

Invariant: before index i is processed, the map contains values seen only at indices < i. Checking before inserting is what prevents using one element twice.

For [2, 7, 11, 15], target 9:

i	value	needed	map before	action
0	2	7	{}	store 2 → 0
1	7	2	{2=0}	return [0, 1]

%%{init: {
  "theme": "base",
  "flowchart": {
    "htmlLabels": false
  },
  "themeVariables": {
    "primaryColor": "#ffffff",
    "secondaryColor": "#ffffff",
    "tertiaryColor": "#ffffff",
    "primaryTextColor": "#222222",
    "primaryBorderColor": "#555555",
    "lineColor": "#555555",
    "edgeLabelBackground": "#ffffff"
  }
}}%%
flowchart TB
  A["Read nums at index i"]
  B["Compute needed = target - nums[i]"]
  C{"Is needed already in the map?"}
  D["YES: return the earlier index and i"]
  E["NO: store nums[i] and i"]

  A --> B
  B --> C
  C --> D
  C --> E
  E --> A

  classDef plain fill:#ffffff,stroke:#555555,stroke-width:1.5px,color:#222222;
  class A,B,C,D,E plain;

3.6 Minimal solution

Java

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class TwoSumSolution {
    static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indexByValue = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int needed = target - nums[i];
            Integer earlierIndex = indexByValue.get(needed);
            if (earlierIndex != null) {
                return new int[] {earlierIndex, i};
            }
            indexByValue.put(nums[i], i);
        }
        throw new IllegalArgumentException("No solution");
    }

    @Test public void ordinaryPair() {
        assertArrayEquals(new int[] {0, 1}, twoSum(new int[] {2, 7, 11, 15}, 9));
    }

    @Test public void usesTwoDifferentEqualValues() {
        assertArrayEquals(new int[] {0, 1}, twoSum(new int[] {3, 3}, 6));
    }

    @Test public void handlesNegativeValues() {
        assertArrayEquals(new int[] {0, 2}, twoSum(new int[] {-4, 8, 3}, -1));
    }

    @Test public void findsPairNearEndOfArray() {
        assertArrayEquals(new int[] {2, 3}, twoSum(new int[] {1, 2, 4, 9}, 13));
    }

    @Test public void handlesTwoZeroValues() {
        assertArrayEquals(new int[] {0, 2}, twoSum(new int[] {0, 4, 0}, 0));
    }

    @Test(expected = IllegalArgumentException.class)
    public void rejectsInputWithNoPair() {
        twoSum(new int[] {1, 2}, 10);
    }

    public static void main(String[] args) {
        JUnitCore.main("TwoSumSolution");
    }
}

Python

import unittest


def two_sum(nums, target):
    index_by_value = {}
    for index, value in enumerate(nums):
        needed = target - value
        if needed in index_by_value:
            return [index_by_value[needed], index]
        index_by_value[value] = index
    raise ValueError("No solution")


class TwoSumTests(unittest.TestCase):
    def test_ordinary_pair(self):
        self.assertEqual([0, 1], two_sum([2, 7, 11, 15], 9))

    def test_uses_two_different_equal_values(self):
        self.assertEqual([0, 1], two_sum([3, 3], 6))

    def test_handles_negative_values(self):
        self.assertEqual([0, 2], two_sum([-4, 8, 3], -1))

    def test_finds_pair_near_end(self):
        self.assertEqual([2, 3], two_sum([1, 2, 4, 9], 13))

    def test_handles_two_zero_values(self):
        self.assertEqual([0, 2], two_sum([0, 4, 0], 0))

    def test_rejects_input_with_no_pair(self):
        with self.assertRaises(ValueError):
            two_sum([1, 2], 10)


if __name__ == "__main__":
    unittest.main()

Rust

use std::collections::HashMap;

pub fn two_sum(nums: &[i32], target: i32) -> Option<[usize; 2]> {
    let mut index_by_value = HashMap::new();

    for (index, &value) in nums.iter().enumerate() {
        let needed = target - value;
        if let Some(&earlier_index) = index_by_value.get(&needed) {
            return Some([earlier_index, index]);
        }
        index_by_value.insert(value, index);
    }

    None
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn ordinary_pair() {
        assert_eq!(Some([0, 1]), two_sum(&[2, 7, 11, 15], 9));
    }

    #[test]
    fn uses_two_different_equal_values() {
        assert_eq!(Some([0, 1]), two_sum(&[3, 3], 6));
    }

    #[test]
    fn handles_negative_values() {
        assert_eq!(Some([0, 2]), two_sum(&[-4, 8, 3], -1));
    }

    #[test]
    fn finds_pair_near_end() {
        assert_eq!(Some([2, 3]), two_sum(&[1, 2, 4, 9], 13));
    }

    #[test]
    fn returns_none_when_no_pair_exists() {
        assert_eq!(None, two_sum(&[1, 2], 10));
    }
}

The test [3, 3], target 6 is especially important: inserting after lookup allows the second 3 to pair with the first.

3.7 High-value tests

Case	Input	Expected	Why
ordinary	[2,7,11,15], 9	[0,1]	basic complement
equal values	[3,3], 6	[0,1]	distinct positions
negatives	[-4,8,3], -1	[0,2]	sign handling
pair near end	[1,2,4,9], 13	[2,3]	full scan
no pair, if allowed	[1,2], 10	exception/sentinel	contract behavior

3.8 Complexity and correctness

Each element causes expected \(O(1)\) map operations, so time is expected \(O(n)\) and space is \(O(n)\). Hash collisions can make worst-case costs less favorable, but expected complexity is the interview convention for HashMap.

When the method returns, the map proves that the earlier value equals target - nums[i]; therefore the two values sum to the target. Their indices differ by the invariant. The guaranteed pair ensures a return before the loop ends.

3.9 If the interviewer pushes

• Without the one-answer guarantee, return all pairs and define whether duplicate value pairs count.
• To avoid arithmetic overflow, use long needed = (long) target - nums[i] and a Map<Long,Integer>.
• If the array is sorted and indices are not required, two pointers use \(O(1)\) extra space.
• If memory is constrained, sort value/index pairs: \(O(n\log n)\) time with less hash-table overhead, but more code.

3.10 TDD interview script

Restate the observable contract first: return two distinct indices, equal values at different positions are allowed, exactly one pair is promised, and the necessary arithmetic fits in the chosen integer type. Mention the implementation’s language-appropriate failure result if the promise is violated, but do not spend the core algorithm time designing unspecified behavior.

Write this test list as comments:

1. Ordinary pair
2. Repeated value
3. Nonadjacent pair
4. Negative values
5. Pair near the end
6. Zero values
7. No pair

Add one focused test at a time and use red–green–refactor: confirm the expected failure, make the smallest general change, run the whole example, and refactor only while green. Compare returned indices by value; tests should not inspect the map.

From book/src, run:

Java

./java/run.sh TwoSumSolution

Python

./python/run.sh two_sum_solution

Rust

./rust/run.sh two_sum_solution

Narrate the crucial choice when the repeated-value test arrives: “I look up the complement before inserting the current value, so one array position cannot match itself.” The later examples triangulate that behavior rather than introducing special cases.

3.10.1 Pseudocode

After the contract and test list, sketch the intended lookup before writing Java:

indexByValue = empty map

for i from 0 through nums.length - 1:
    needed = target - nums[i]
    if needed is in indexByValue:
        return [indexByValue[needed], i]
    indexByValue[nums[i]] = i

throw no-solution exception

The invariant is: before processing i, the map contains values from indices strictly less than i. Therefore any returned indices are distinct.

3.10.2 TDD sequence

Step	Test code added	Production code added or changed
1. First complement	ordinaryPair	Introduce the scan, compute needed, and return the earlier and current indices when a complement is found.
2. Distinct positions	usesTwoDifferentEqualValues	Perform lookup before insertion. This rejects an accidental [0,0] self-match and permits two equal values at different indices.
3. Full scan state	handlesNegativeValues	Preserve all earlier values in a HashMap; this also verifies a nonadjacent pair and signed arithmetic.
4. Late result	findsPairNearEndOfArray	Confirm that the method continues scanning and returns a pair discovered at the end. No new branch should be needed.
5. Zero boundary	handlesTwoZeroValues	Triangulate complement lookup when both the value and target are zero.
6. Violated guarantee	no-pair case	Add the language-appropriate failure result after the loop. This documents the implementation’s response when the promised pair is absent.

The progression uses behavior-focused examples and triangulation to expose the ordering invariant. The final implementation remains a single pass without tests coupled to HashMap internals.