Two Sum

Problem

Given an array of integers and a target, return the indices of the two numbers that add up to the target. Each input has exactly one solution and you may not use the same element twice.

Approach

Single-pass hash map. For each element, compute the complement (target - current). If the complement is already in the map, return both indices. Otherwise store current value -> index.

When to Use

Any problem asking "find pair with property X" — hash map for O(1) lookups. Also: complement problems, two-number sum/difference/product.

Complexity

Time	O(n)
Space	O(n)

Implementation

SolutionTestsChallenge

two_sum

Two Sum — find two indices whose values sum to target.

Problem

Given an array of integers and a target, return the indices of the two numbers that add up to the target. Each input has exactly one solution and you may not use the same element twice.

Approach

Single-pass hash map. For each element, compute the complement (target - current). If the complement is already in the map, return both indices. Otherwise store current value -> index.

When to use

Any problem asking "find pair with property X" — hash map for O(1) lookups. Also: complement problems, two-number sum/difference/product.

Complexity

Time: O(n) Space: O(n)

two_sum

two_sum(
    nums: Sequence[int], target: int
) -> tuple[int, int]

Return indices of two elements that sum to target.

two_sum([2, 7, 11, 15], 9) (0, 1)

Source code in src/algo/arrays/two_sum.py

def two_sum(nums: Sequence[int], target: int) -> tuple[int, int]:
    """Return indices of two elements that sum to *target*.

    >>> two_sum([2, 7, 11, 15], 9)
    (0, 1)
    """
    seen: dict[int, int] = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return (seen[complement], i)
        seen[n] = i

    msg = "no two elements sum to target"
    raise ValueError(msg)

tests/arrays/test_two_sum.py

"""Tests for the two-sum problem."""

import pytest
from hypothesis import given
from hypothesis import strategies as st

from algo.arrays.two_sum import two_sum


class TestTwoSum:
    def test_basic(self) -> None:
        assert two_sum([2, 7, 11, 15], 9) == (0, 1)

    def test_target_at_end(self) -> None:
        assert two_sum([3, 2, 4], 6) == (1, 2)

    def test_negative_numbers(self) -> None:
        assert two_sum([-3, 4, 3, 90], 0) == (0, 2)

    def test_same_value_twice(self) -> None:
        assert two_sum([3, 3], 6) == (0, 1)

    def test_large_target(self) -> None:
        assert two_sum([1, 5, 100, 200], 300) == (2, 3)

    def test_no_solution_raises(self) -> None:
        with pytest.raises(ValueError):
            two_sum([1, 2, 3], 100)

    @given(
        data=st.lists(
            st.integers(min_value=-500, max_value=500),
            min_size=2,
            max_size=50,
            unique=True,
        ),
    )
    def test_returned_indices_sum_to_target(self, data: list[int]) -> None:
        target = data[0] + data[1]
        i, j = two_sum(data, target)
        assert i != j
        assert data[i] + data[j] == target

Implement it yourself

Run: just challenge arrays two_sum

Then implement the functions to make all tests pass. Use just study arrays for watch mode.

Reveal Solution

two_sum

Two Sum — find two indices whose values sum to target.

Problem

Given an array of integers and a target, return the indices of the two numbers that add up to the target. Each input has exactly one solution and you may not use the same element twice.

Approach

Single-pass hash map. For each element, compute the complement (target - current). If the complement is already in the map, return both indices. Otherwise store current value -> index.

When to use

Any problem asking "find pair with property X" — hash map for O(1) lookups. Also: complement problems, two-number sum/difference/product.

Complexity

Time: O(n) Space: O(n)

two_sum

two_sum(
    nums: Sequence[int], target: int
) -> tuple[int, int]

Return indices of two elements that sum to target.

two_sum([2, 7, 11, 15], 9) (0, 1)

Source code in src/algo/arrays/two_sum.py

def two_sum(nums: Sequence[int], target: int) -> tuple[int, int]:
    """Return indices of two elements that sum to *target*.

    >>> two_sum([2, 7, 11, 15], 9)
    (0, 1)
    """
    seen: dict[int, int] = {}
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return (seen[complement], i)
        seen[n] = i

    msg = "no two elements sum to target"
    raise ValueError(msg)