Two sum: remember the useful past

Derive the representation

Start with each possible right endpoint j, then try all earlier i in order. That baseline directly implements the tie rule but performs O(n²) comparisons. A candidate should identify the repeated question: “Did target - nums[j] appear earlier, and where did it first appear?” visited answers that question without rescanning the prefix. Each encountered value maps to its first index.

The invariant is that, before processing j, the map contains each earlier value and its first index. Lookup before insertion prevents using j twice. Keeping the first index preserves the second tie rule; returning on the first successful right endpoint preserves the first. If lookup fails, record this value and index unless the value already has an earlier index. If every lookup fails, every eligible pair was ruled out when its right endpoint was visited. Hash lookup has expected constant cost, so validation plus search cost expected O(n) time and O(n) auxiliary space; adversarial hash behavior is not a promised worst-case O(n) bound. No result-size term is needed for one pair.

Follow-up 1: return every index pair

Predict the state change before reading the table. Storing one index now loses answers. Map each encountered value to all earlier indices and emit a pair for each complement match. For [3, 3, 3], target 6:

The expected bound becomes O(n + p), where p is the number of returned pairs; p can be quadratic. A generator reduces retained output, not required work. Distinct value pairs would require a different deduplication contract.

Follow-up 2: amounts arrive forever

Now accept add(amount) and ask whether a pair exists among the most recent three arrivals. Redraw ownership of history: the old permanent map is incorrect because expired values can produce false matches.

Counts, rather than a set, preserve duplicates during eviction. If an amount is its own complement, require count at least two. A senior candidate separates index-pair, value-pair, and existence semantics and explains output cost. A lead candidate additionally defines ordering, retention, and backpressure for the streaming API; the in-memory solution supplies no cross-process ordering.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/01-two-sum
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

def _integers(values):
    if not isinstance(values, (list, tuple)) or any(type(x) is not int for x in values):
        raise ValueError("expected a list or tuple of integers, excluding bool")

def two_sum(nums, target):
    _integers(nums)
    if type(target) is not int:
        raise ValueError("target must be an integer")
    visited = {}
    for j, value in enumerate(nums):
        complement = target - value
        if complement in visited:
            return visited[complement], j
        visited.setdefault(value, j)
    return None

import itertools
import unittest
from solution import two_sum

class TwoSumTests(unittest.TestCase):
    def test_contract(self):
        self.assertEqual(two_sum([3, 3, 2], 6), (0, 1))
        self.assertEqual(two_sum([1, 1, 3], 4), (0, 2))
        self.assertIsNone(two_sum([3], 6))
        nums = [-3, 8, 4]
        self.assertEqual(two_sum(nums, 5), (0, 1))
        self.assertEqual(nums, [-3, 8, 4])
        for nums, target in [(None, 2), ([True], 2), ([1], 2.0)]:
            with self.assertRaises(ValueError):
                two_sum(nums, target)

    def test_exhaustive_pair_oracle(self):
        for n in range(6):
            for values in itertools.product(range(-1, 2), repeat=n):
                for target in range(-2, 3):
                    expected = next(((i, j) for j in range(n) for i in range(j)
                                     if values[i] + values[j] == target), None)
                    self.assertEqual(two_sum(values, target), expected)

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