LeetCode 170 – Two Sum III – Data Structure Design

Two Sum III is not an algorithms problem — it is a question about which operation you expect to be called more often. There are two reasonable designs with opposite costs, and the answer the interviewer wants is not one of them but the sentence that chooses between them.

The problem

Design a structure supporting:

add(number) — insert a number into the collection.
find(value) — return whether any pair of numbers in the collection sums to value.

add(1); add(3); add(5);
find(4)  -> true    1 + 3
find(7)  -> false
find(8)  -> true    3 + 5

add(0); add(0);
find(0)  -> true    0 + 0, using the two DIFFERENT zeros
find(0) with only one 0 added -> false

A pair means two distinct positions, not two distinct values. That is the case the whole problem turns on.

The design choice

	`add`	`find`	Space
Count map, search on find	`O(1)`	`O(n)`	`O(n)`
Precompute every pair sum on add	`O(n)`	`O(1)`	`O(n²)`

Neither is better in the abstract. Ask which is called more:

Many adds, few finds — the count map. Adding is free, and you pay only for the searches you actually do.
Few adds, many finds — precompute. The O(n²) space is the cost, and on a large collection it is prohibitive.

Asking that question before writing anything is the answer to this problem. Picking one silently is the mistake, however good the implementation.

In practice the count map is the default, because O(n²) space is a much harder sell than O(n) time. Say that, then build it.

The duplicate case

With a count map, find(value) scans the keys looking for value − key. When those are the same number, one copy is not enough:

find(4) with {2: 1}    -> false   only ONE 2; a pair needs two
find(4) with {2: 2}    -> true    two distinct positions

so:  if key * 2 == value   ->  need count[key] >= 2
     otherwise             ->  need complement present at all

This is why the structure counts rather than merely remembering which numbers it has seen. A plain set would report find(4) true after a single add(2), and it is the first thing an interviewer tests.

Java

class TwoSum {
    // Counts, not a set: a pair may need two copies of the same number.
    private final Map<Integer, Integer> counts = new HashMap<>();

    public void add(int number) {
        counts.merge(number, 1, Integer::sum);
    }

    public boolean find(int value) {
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            int number = entry.getKey();
            int complement = value - number;

            if (complement == number) {
                if (entry.getValue() >= 2) return true;   // needs two copies
            } else if (counts.containsKey(complement)) {
                return true;
            }
        }

        return false;
    }
}

Iterating entrySet() rather than keySet() gives the count without a second lookup, which matters because the complement branch already does one.

value - number can overflow when both are near the integer limits. LeetCode's constraints keep it in range; in production the parameters would be long, and noticing that is worth a sentence — it is the same class of bug as the subtraction comparator in Merge Intervals.

Python

from collections import defaultdict


class TwoSum:
    def __init__(self):
        self.counts = defaultdict(int)

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

    def find(self, value: int) -> bool:
        for number, count in self.counts.items():
            complement = value - number

            if complement == number:
                if count >= 2:            # a pair needs two copies
                    return True
            elif complement in self.counts:
                return True

        return False

Iterate list(self.counts.items()) if anything could mutate the dictionary during the scan. Nothing does here, but a defaultdict is one accidental self.counts[x] lookup away from inserting a key mid-iteration and raising RuntimeError — a real hazard worth knowing about the class you chose.

The precompute alternative

If find dominates, store every achievable sum as numbers arrive:

add(number):
    for each existing n:  sums.add(n + number)     O(n)
    numbers.append(number)

find(value):  return value in sums                O(1)

The duplicate case handles itself: adding a second 2 pairs it with the first, so 4 enters the set naturally. That is a nice property and it is bought with O(n²) memory, which is the reason this is the minority answer.

Complexity

Design	`add`	`find`	Space
Count map	`O(1)`	`O(n)` distinct values	`O(n)`
Precomputed sums	`O(n)`	`O(1)`	`O(n²)`

find is linear in the number of distinct values, not the number of adds — so a million copies of the same number still scans one key. Worth stating precisely; it is a real difference on skewed data.

How this differs from Two Sum

Two Sum (1) is handed the whole array at once and can do a single pass with a map, because it knows the complete input. Here the input arrives incrementally and the target is not known until find is called, so no single pass exists to make.

That contrast is the reason this problem is a design question with an "III" in its name rather than a variant: the algorithm is unchanged and the access pattern is what moved. Most design questions are like that — the same data, a different sequence of demands.

What the interviewer is checking

That you ask which operation dominates before choosing.
Counts rather than a set, and the 2 × key == value case.
That both designs are on the table with their trade-offs named.
find before any add, and with a single element.
That find is linear in distinct values, not in adds.
Overflow in value - number.
Why this is a design question rather than a repeat of problem 1.