LeetCode 170: Two Sum III - Data Structure Design

Problem Restatement

We need to design a data structure that supports two operations:

add(number)
find(value)

The operations behave like this:

The same number may be added multiple times.

The pair must use two different occurrences unless the number appears at least twice.

For example:

add(1)
add(3)
add(5)

Then:

find(4) -> True

because:

1 + 3 = 4

But:

find(7) -> False

because no pair sums to 7.

Input and Output

Example class shape:

class TwoSum:

    def add(self, number: int) -> None:
        ...

    def find(self, value: int) -> bool:
        ...

Examples

Example sequence:

twoSum = TwoSum()

twoSum.add(1)
twoSum.add(3)
twoSum.add(5)

Now:

twoSum.find(4)

returns:

True

because:

1 + 3 = 4

Next:

twoSum.find(7)

returns:

False

because no valid pair exists.

Another example:

twoSum.add(3)
twoSum.add(3)

Then:

twoSum.find(6)

returns:

True

because two occurrences of 3 exist.

First Thought: Store All Numbers in a List

A direct solution is:

class TwoSum:

    def __init__(self):
        self.nums = []

    def add(self, number: int) -> None:
        self.nums.append(number)

    def find(self, value: int) -> bool:
        n = len(self.nums)

        for i in range(n):
            for j in range(i + 1, n):
                if self.nums[i] + self.nums[j] == value:
                    return True

        return False

This works, but find takes:

O(n^2)

which is too slow.

We can do better with hashing.

Key Insight

Use a frequency map.

Store:

number -> count

Then for each number x, the required partner is:

y = value - x

There are two cases.

This lets us answer find in linear time.

Algorithm

Use a hash map:

self.count

For add(number):

1. Increment its frequency.

For find(value):

1. Loop through all stored numbers x.
2. Compute:

y = value - x

3. If x != y, return True when y exists.
4. If x == y, return True only when the count is at least 2.

If no valid pair exists, return False.

Walkthrough

Start:

add(1)
add(3)
add(5)

Frequency map:

{
    1: 1,
    3: 1,
    5: 1
}

Call:

find(4)

Check x = 1:

y = 4 - 1 = 3

Since 3 exists, return:

True

Now check:

find(7)

Check:

Return:

False

Correctness

The frequency map stores exactly how many times each number has been added.

During find(value), for every stored number x, the algorithm checks whether the complementary value:

y = value - x

exists.

If x != y, then one occurrence of x and one occurrence of y form a valid pair whose sum is value.

If x == y, then the pair uses the same value twice, so at least two occurrences are required. The algorithm checks this using the stored count.

If the algorithm returns True, a valid pair exists by construction.

If the algorithm finishes without returning True, then no stored number has a valid complementary partner, so no valid pair exists.

Therefore, the algorithm returns the correct result for every find call.

Complexity

Let n be the number of distinct stored values.

Hash table operations are average-case constant time.

Implementation

class TwoSum:

    def __init__(self):
        self.count = {}

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

    def find(self, value: int) -> bool:
        for x in self.count:
            y = value - x

            if x != y:
                if y in self.count:
                    return True
            else:
                if self.count[x] >= 2:
                    return True

        return False

Code Explanation

The constructor creates the frequency map:

self.count = {}

The add operation increments the count:

self.count[number] = self.count.get(number, 0) + 1

Inside find, loop through every stored value:

for x in self.count:

Compute the needed partner:

y = value - x

If the two numbers are different:

if x != y:

we only need the partner to exist:

if y in self.count:
    return True

If the numbers are the same:

else:

we need at least two copies:

if self.count[x] >= 2:
    return True

If no valid pair is found:

return False

Alternative Design: Fast find

We can also optimize for fast find.

Idea:

Store every possible pair sum in a set.

When adding a new number, combine it with all previous numbers and store the sums.

Then find(value) becomes:

value in sums

This is useful when find is called much more often than add.

Testing

def run_tests():
    ts = TwoSum()

    ts.add(1)
    ts.add(3)
    ts.add(5)

    assert ts.find(4) is True
    assert ts.find(7) is False

    ts = TwoSum()

    ts.add(3)
    ts.add(3)

    assert ts.find(6) is True
    assert ts.find(7) is False

    ts = TwoSum()

    ts.add(-1)
    ts.add(1)

    assert ts.find(0) is True

    ts = TwoSum()

    ts.add(0)
    ts.add(0)

    assert ts.find(0) is True

    ts = TwoSum()

    ts.add(2)
    ts.add(4)
    ts.add(6)

    assert ts.find(8) is True
    assert ts.find(5) is False

    print("all tests passed")

run_tests()