Two-sum in Python: trade a little memory for one pass

Problem. Finding two values that add to a target is often written as a nested search, which checks the same list against itself again and again. Baseline complexity. The exact nested-loop programme below makes n(n – 1) / 2 comparisons in a no-pair case, so its time is O(n²) and its extra space is O(1). Solution. Keep earlier values in a dictionary and look up each value’s complement while scanning once. The expected time is O(n), with O(n) extra space. Measured result. On this Raspberry Pi run, the dictionary version was 260.35x faster at n=1,000, 503.33x faster at n=2,500, and 1,086.25x faster at n=5,000 for the measured no-pair inputs.

Reproduce the result

Complete code

from __future__ import annotations
import platform
import statistics
import sys
import timeit
def find_pair_quadratic(values: list[int], target: int) -> tuple[int, int] | None:
    """Return the first pair of indices whose values add to target."""
    for left_index, left_value in enumerate(values):
        for right_index in range(left_index + 1, len(values)):
            if left_value + values[right_index] == target:
                return left_index, right_index
    return None
def find_pair_hash(values: list[int], target: int) -> tuple[int, int] | None:
    """Use a dictionary of earlier values to find a complementary value."""
    seen: dict[int, int] = {}
    for index, value in enumerate(values):
        complement = target - value
        if complement in seen:
            return seen[complement], index
        seen[value] = index
    return None
def quadratic_work(values: list[int], target: int) -> tuple[tuple[int, int] | None, int]:
    comparisons = 0
    for left_index, left_value in enumerate(values):
        for right_index in range(left_index + 1, len(values)):
            comparisons += 1
            if left_value + values[right_index] == target:
                return (left_index, right_index), comparisons
    return None, comparisons
def hash_work(values: list[int], target: int) -> tuple[tuple[int, int] | None, int, int]:
    lookups = 0
    stores = 0
    seen: dict[int, int] = {}
    for index, value in enumerate(values):
        complement = target - value
        lookups += 1
        if complement in seen:
            return (seen[complement], index), lookups, stores
        seen[value] = index
        stores += 1
    return None, lookups, stores
def no_pair_input(size: int) -> list[int]:
    return list(range(1, 2 * size, 2))
def median(values: list[float]) -> float:
    return statistics.median(values)
examples = [
    ([2, 7, 11, 15], 9, (0, 1)),
    ([3, 3], 6, (0, 1)),
    ([1], 2, None),
    ([], 0, None),
]
for values, target, expected in examples:
    assert find_pair_quadratic(values, target) == expected
    assert find_pair_hash(values, target) == expected
print("correctness=passed")
print(f"python={sys.version.split()[0]}")
print(f"platform={platform.platform()}")
print("case=no_pair_positive_odd_values,target=-1")
print("timing_policy=5 repeats, number=1, timeit.default_timer")
for size in (1_000, 2_500, 5_000):
    values = no_pair_input(size)
    target = -1
    quadratic_result, comparisons = quadratic_work(values, target)
    hash_result, lookups, stores = hash_work(values, target)
    assert quadratic_result == hash_result == None
    assert comparisons == size * (size - 1) // 2
    assert lookups == stores == size
    quadratic_samples = timeit.repeat(
        lambda: find_pair_quadratic(values, target), repeat=5, number=1
    )
    hash_samples = timeit.repeat(
        lambda: find_pair_hash(values, target), repeat=5, number=1
    )
    quadratic_median = median(quadratic_samples)
    hash_median = median(hash_samples)
    print(
        f"n={size} comparisons={comparisons} dict_lookups={lookups} "
        f"dict_stores={stores} quadratic_samples_s="
        + ",".join(f"{sample:.9f}" for sample in quadratic_samples)
        + " hash_samples_s="
        + ",".join(f"{sample:.9f}" for sample in hash_samples)
        + f" median_ratio={quadratic_median / hash_median:.2f}x"
    )

Output

correctness=passed
python=3.13.5
platform=Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41
case=no_pair_positive_odd_values,target=-1
timing_policy=5 repeats, number=1, timeit.default_timer
n=1000 comparisons=499500 dict_lookups=1000 dict_stores=1000 quadratic_samples_s=0.076262562,0.076417412,0.076176525,0.115778099,0.081409390 hash_samples_s=0.000380978,0.000293516,0.000294628,0.000291257,0.000291571 median_ratio=260.35x
n=2500 comparisons=3123750 dict_lookups=2500 dict_stores=2500 quadratic_samples_s=0.488836379,0.486464194,0.487514445,0.483838085,0.489095802 hash_samples_s=0.001071640,0.001050825,0.000895715,0.000968585,0.000886178 median_ratio=503.33x
n=5000 comparisons=12497500 dict_lookups=5000 dict_stores=5000 quadratic_samples_s=1.918385588,1.918246886,1.931588002,1.934961012,1.918098109 hash_samples_s=0.001956114,0.001766060,0.001750819,0.001647691,0.001799393 median_ratio=1086.25x

Environment

The run used CPython 3.13.5 on Linux 6.12.47+rpt-rpi-v8, aarch64, with glibc 2.41. The programme uses only the Python standard library.

Methodology

The correctness checks cover a normal pair, a duplicate pair, a one-item input, and an empty input. The timing cases contain positive odd integers and use target=-1, so no pair exists and both searches traverse the full workload. The sizes are 1,000, 2,500, and 5,000. Each timing uses timeit.repeat with five repeats and one call per repeat; the printed ratio divides the median quadratic time by the median dictionary time. Python’s timeit documentation states that the default timer returns seconds as a float and that setup time is excluded from the timed run.^[3]

Input construction happens outside the timed call. The script does not measure memory, process start-up, list creation, or dictionary allocation separately. The reported numbers therefore compare the two search functions under one interpreter and one input shape. They are useful for this run, not a universal speed ranking.

The problem

The task is the familiar two-sum question: given a sequence of numbers and a target, return indices for two different elements whose values add to that target. For [2, 7, 11, 15] and 9, the answer is (0, 1).

A first implementation usually picks one element, then checks every later element until it finds a match. That is easy to inspect and hard to misuse. It also repeats work. If the first pass checks whether the first value pairs with every later item, the next pass starts over with the second value, even though the earlier values have already been considered.

The implementation here returns the first pair encountered by its scan order. If several valid pairs exist, the two versions need not choose the same pair unless their search order is kept identical. The correctness examples check the returned pair explicitly.

Baseline complexity

The baseline has two loops. For each left index, the inner loop visits every larger index. On an input with no solution, the number of additions and comparisons is

(n - 1) + (n - 2) + ... + 1 = n(n - 1) / 2.

At n=5,000, that is 12,497,500 comparisons, which is the count printed by the executed programme. The algorithm therefore takes O(n²) time in the worst case and uses O(1) auxiliary space apart from the input and returned tuple.

The formula describes the algorithm, not every cost in the Python interpreter. Each comparison also involves Python loop control, integer addition, list indexing and a conditional branch. Those costs do not change the quadratic growth, but they do affect the seconds on the stopwatch.

The solution

The dictionary version keeps an invariant: before processing values[index], seen contains the values from earlier positions and the index at which each value was seen. For the current value value, the required partner is target - value.

The function checks that complement before storing the current value. That order matters. It prevents an element from pairing with itself, while still allowing duplicates such as [3, 3] with target 6. Python dictionaries map hashable keys to values, so the input elements used as keys must be hashable.^[1]

The dictionary operations have expected O(1) lookup and insertion time in the usual CPython model, giving expected O(n) time for the scan and O(n) additional space for seen.^[2] The same reference lists O(n) as the worst case for a dictionary lookup, and its average-case note depends on hash collisions remaining uncommon.^[2]

The programme counts one dictionary membership check and one store for every no-pair input element. At n=5,000, that is 5,000 lookups and 5,000 stores instead of 12,497,500 pair comparisons. The dictionary has not made the input disappear. It has changed the repeated search into a record of what the scan has already learned.

What the measurement shows

The ratio rises with input size because the baseline’s comparison count grows quadratically while the dictionary version’s scan grows linearly. The absolute timings still vary with system load, CPU frequency and interpreter state. Even within the first five samples, the quadratic run at n=1,000 includes one noticeably slower sample than its neighbours.

The result is conditional on the tested case. A pair found near the start can make the nested search stop early. A dictionary lookup is also an average-case claim, not a promise that every possible key type or hash distribution behaves identically.^[2] The benchmark uses small integers, a single process and a no-pair workload, so it does not settle the best choice for every application.

Where it stops helping

The dictionary approach costs memory proportional to the number of values scanned. That trade is usually sensible when the sequence is large and the result is small, but it is a poor fit when memory is tight or the input is a one-shot stream that cannot be retained in the chosen form.

It also assumes that values can be used as dictionary keys. Lists and dictionaries are not hashable, for example, so a pair-search function over mutable records needs a different key or a separate representation.^[1]

The nested version remains useful when the input is tiny, when clarity matters more than throughput, or when the data is expensive to hash and the scan usually finds a pair immediately. The right comparison is the one that matches the actual distribution of inputs, the expected location of a match, and the memory budget.

For the no-pair workload measured here, the dictionary wins by a large margin because it remembers each earlier value once. The code still scans every element, but it no longer asks every pair to introduce itself.

Sources

[1] Built-in Types: dict — Python 3.14.7 documentation

[2] TimeComplexity — Python Wiki

[3] timeit — Measure execution time of small code snippets — Python 3.14.7 documentation