LeetCode 170 - Two Sum III - Data structure design

LeetCode Problem 170

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Two Pointers, Design, Data Stream

Solution

Problem Understanding

The problem asks us to design a data structure that supports two operations efficiently over a stream of integers.

The first operation, add(number), inserts a number into the data structure. Numbers may appear multiple times, so duplicates must be handled correctly.

The second operation, find(value), checks whether there exists any pair of numbers already added whose sum equals the given target value. The method should return true if such a pair exists and false otherwise.

This is different from the classic Two Sum problem because the numbers are not given all at once. Instead, they arrive incrementally through repeated calls to add. We must maintain enough information so that future find calls can be answered efficiently.

For example, suppose the following operations occur:

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

The internal collection now contains [1, 3, 5].

If we call:

find(4)

the answer is true because 1 + 3 = 4.

If we call:

find(7)

the answer is false because no pair sums to 7.

The constraints are relatively small, with at most 10^4 calls total to add and find. Even though this is not extremely large, we still want a solution that avoids repeatedly checking every possible pair from scratch.

An important detail is that the same number may need to be used twice only if it appears at least twice in the data structure. For example:

add(3)
find(6)

should return false, because there is only one 3.

But:

add(3)
add(3)
find(6)

should return true.

Negative numbers are also allowed, so the algorithm cannot rely on positive-only assumptions such as sorted order or two-pointer expansion.

Approaches

Brute Force Approach

The most straightforward solution is to store every inserted number in a list.

Whenever find(value) is called, we examine every possible pair of numbers in the list and check whether their sum equals value.

For example, if the numbers are:

[1, 3, 5]

then find(4) would check:

• 1 + 3
• 1 + 5
• 3 + 5

until it finds a valid pair.

This approach is correct because it explicitly tests every possible combination. If a valid pair exists, it will eventually be found.

However, this becomes inefficient as the number of stored values grows. If there are n numbers, then checking all pairs requires O(n^2) time in the worst case.

Since find may be called many times, repeatedly scanning all pairs is unnecessarily expensive.

Optimal Approach

A better solution uses a hash map to store the frequency of each number.

The key insight is that for any number x, the value needed to complete the target sum is:

complement = target - x

If both x and complement exist in the data structure, then we have found a valid pair.

The hash map allows constant-time lookup of complements.

For example, suppose the frequency map is:

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

To evaluate find(4):

• Check 1, complement is 3
• 3 exists in the map
• Return true

We must also carefully handle the case where:

x == complement

In that situation, we need at least two occurrences of the number.

For example:

find(6)

requires two 3s.

This approach reduces find to O(n) time while keeping add at O(1) time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	add: O(1), find: O(n^2)	O(n)	Stores all numbers and checks every pair
Optimal	add: O(1), find: O(n)	O(n)	Uses hash map frequency counting

Algorithm Walkthrough

1. Initialize a hash map called counts.

The keys are numbers that have been added, and the values are how many times each number appears.

Example:

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

2. When add(number) is called, increment the frequency count for that number.

If the number has not appeared before, initialize its count to 1.

This operation is efficient because hash map insertion and lookup are constant time on average. 3. When find(value) is called, iterate through every unique number in the hash map.

For each number:

complement = value - number

4. Check whether the complement exists in the hash map.

If it does not exist, continue to the next number. 5. If the complement exists, there are two possible situations.

If:

number != complement

then we already have two distinct numbers whose sum equals the target.

Return true. 6. If:

number == complement

then we need at least two copies of that number.

For example:

3 + 3 = 6

requires the count of 3 to be at least 2. 7. If no valid pair is found after checking all numbers, return false.

Why it works

The algorithm works because every valid pair must consist of some number x and its complement value - x.

By iterating through every stored number and checking whether its complement exists, we exhaustively test all possible valid pairs. The hash map guarantees fast complement lookup, and the duplicate-count check correctly handles pairs where both numbers are the same.

Therefore, the algorithm always returns the correct result.

Python Solution

class TwoSum:

    def __init__(self):
        self.counts: dict[int, int] = {}

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

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

            if complement not in self.counts:
                continue

            if complement != number:
                return True

            if self.counts[number] >= 2:
                return True

        return False

# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# obj.add(number)
# param_2 = obj.find(value)

The implementation begins by creating a dictionary called counts. This dictionary stores how many times each number has been added.

The add method updates the frequency count. If the number already exists, its count increases by one. Otherwise, it is inserted with count 1.

The find method iterates through every unique number currently stored. For each number, it computes the complement needed to reach the target value.

The hash map allows constant-time checking of whether the complement exists.

The implementation carefully distinguishes between two cases:

• The complement is a different number
• The complement is the same number

If the numbers are different, the pair is immediately valid.

If they are the same, the code verifies that the frequency count is at least 2.

If no valid pair exists, the method returns False.

Go Solution

type TwoSum struct {
	counts map[int]int
}

func Constructor() TwoSum {
	return TwoSum{
		counts: make(map[int]int),
	}
}

func (this *TwoSum) Add(number int) {
	this.counts[number]++
}

func (this *TwoSum) Find(value int) bool {
	for number := range this.counts {
		complement := value - number

		count, exists := this.counts[complement]

		if !exists {
			continue
		}

		if complement != number {
			return true
		}

		if count >= 2 {
			return true
		}
	}

	return false
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(number);
 * param_2 := obj.Find(value);
 */

The Go implementation mirrors the Python approach closely.

Instead of Python dictionaries, Go uses a map[int]int to store frequencies.

One small difference is that Go map lookups return two values:

value, exists := map[key]

The exists boolean is used to determine whether the complement is present.

Go integers safely support the problem constraints, so no additional overflow handling is necessary.

Worked Examples

Example 1

Operations:

add(1)
add(3)
add(5)
find(4)
find(7)

Step-by-step state

Operation	Hash Map State	Result
add(1)	{1: 1}	-
add(3)	{1: 1, 3: 1}	-
add(5)	{1: 1, 3: 1, 5: 1}	-

Now evaluate:

find(4)

Current Number	Complement	Exists?	Action
1	3	Yes	Return true

Result:

true

Now evaluate:

find(7)

Current Number	Complement	Exists?	Valid Pair?
1	6	No	No
3	4	No	No
5	2	No	No

No valid pair exists.

Result:

false

Duplicate Example

Operations:

add(3)
add(3)
find(6)

Step-by-step state

Operation	Hash Map State
add(3)	{3: 1}
add(3)	{3: 2}

Now evaluate:

find(6)

Current Number	Complement	Count	Valid?
3	3	2	Yes

Result:

true

Complexity Analysis

Measure	Complexity	Explanation
Time	add: O(1), find: O(n)	add updates a hash map entry, find scans all unique numbers
Space	O(n)	Stores frequency counts for all inserted numbers

The add operation is constant time because hash map insertion and update are efficient on average.

The find operation iterates through all unique numbers stored in the map. For each number, complement lookup is constant time, resulting in overall O(n) complexity.

The space complexity is linear because every distinct number may need to be stored in the frequency map.

Test Cases

# Provided example
ts = TwoSum()
ts.add(1)
ts.add(3)
ts.add(5)

assert ts.find(4) is True      # 1 + 3 = 4
assert ts.find(7) is False     # no valid pair

# Duplicate values
ts = TwoSum()
ts.add(3)
ts.add(3)

assert ts.find(6) is True      # 3 + 3 = 6

# Single element cannot form pair
ts = TwoSum()
ts.add(5)

assert ts.find(10) is False    # only one 5 exists

# Negative numbers
ts = TwoSum()
ts.add(-1)
ts.add(-2)
ts.add(-3)

assert ts.find(-5) is True     # -2 + -3 = -5
assert ts.find(0) is False     # no pair sums to 0

# Mixed positive and negative
ts = TwoSum()
ts.add(-4)
ts.add(10)
ts.add(6)

assert ts.find(2) is True      # -4 + 6 = 2

# Multiple duplicates
ts = TwoSum()
ts.add(2)
ts.add(2)
ts.add(2)

assert ts.find(4) is True      # two 2s exist

# Zero handling
ts = TwoSum()
ts.add(0)
ts.add(0)

assert ts.find(0) is True      # 0 + 0 = 0

# Large values within constraints
ts = TwoSum()
ts.add(100000)
ts.add(-100000)

assert ts.find(0) is True      # large opposite values

# No numbers added
ts = TwoSum()

assert ts.find(1) is False     # empty structure

Test	Why
Basic example	Verifies normal functionality
Duplicate values	Ensures identical-number pairing works correctly
Single element	Prevents using the same element twice incorrectly
Negative numbers	Confirms support for negative values
Mixed positive and negative	Tests complement logic across signs
Multiple duplicates	Verifies frequency counting
Zero handling	Ensures zero-pair cases work
Large values	Confirms boundary-safe arithmetic
Empty structure	Ensures correct behavior with no data

Edge Cases

Using the Same Number Twice

One of the most common mistakes is incorrectly allowing a single occurrence of a number to form a pair with itself.

For example:

add(3)
find(6)

should return false, not true.

The implementation handles this by checking whether the frequency count is at least 2 when:

number == complement

This guarantees that two separate occurrences exist.

Duplicate Insertions

The data structure must support repeated numbers correctly.

For example:

add(2)
add(2)
find(4)

should return true.

A simple set would fail here because sets discard duplicates. Using a frequency map preserves occurrence counts and correctly handles repeated values.

Negative Numbers and Zero

Some incorrect solutions assume all numbers are positive or rely on sorted ordering behavior.

The problem allows values such as:

-100000
0
100000

The hash map approach works uniformly for all integers because complement calculation:

complement = value - number

remains valid regardless of sign.

This ensures correct handling of negative targets, mixed-sign pairs, and zero-sum cases.