Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.
Implement the TwoSum class:
TwoSum() Initializes the TwoSum object, with an empty array initially.void add(int number) Adds number to the data structure.boolean find(int value) Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.
Example 1:
Input ["TwoSum", "add", "add", "add", "find", "find"] [[], [1], [3], [5], [4], [7]] Output [null, null, null, null, true, false] Explanation TwoSum twoSum = new TwoSum(); twoSum.add(1); // [] --> [1] twoSum.add(3); // [1] --> [1,3] twoSum.add(5); // [1,3] --> [1,3,5] twoSum.find(4); // 1 + 3 = 4, return true twoSum.find(7); // No two integers sum up to 7, return false
Constraints:
-105 <= number <= 105-231 <= value <= 231 - 1104 calls will be made to add and find.Problem Overview: Design a data structure that supports two operations: add(number) to store a value from a data stream, and find(value) to check whether any two stored numbers sum to the given target. The structure must support frequent inserts and efficient pair-sum queries.
Approach 1: Brute Force List Scan (Add: O(1), Find: O(n^2) time, O(n) space)
Store every number in a simple list when add is called. For the find operation, iterate through all pairs in the list and check whether their sum equals the target. This means two nested loops or checking every combination of elements. The approach is straightforward but inefficient because each query may require scanning all pairs. With many numbers or frequent find calls, the quadratic time quickly becomes a bottleneck.
Approach 2: Hash Table Frequency Map (Add: O(1), Find: O(n) time, O(n) space)
Use a frequency map where the key is the number and the value is how many times it appears. When add(number) runs, increment the count in the hash table. For find(value), iterate through the keys in the map and compute the complement value - num. A constant-time hash lookup checks whether the complement exists.
If the complement is different from the current number, a single occurrence is enough. If the complement equals the same number (for example checking 4 + 4 = 8), the frequency must be at least two. This avoids incorrectly using the same element twice. The hash lookup makes each complement check O(1), so the full scan of stored values takes O(n).
This design works well for a continuous data stream. Insertions remain constant time, and each query only scans unique values. The solution relies on fast lookups provided by a hash table and cleanly models the operations required in the design problem.
Recommended for interviews: Interviewers expect the hash table frequency approach. It demonstrates that you understand complement-based pair searching and how to adapt the classic Two Sum technique to a dynamic data structure. Mentioning the brute force approach first shows baseline reasoning, but implementing the hash map design shows stronger problem-solving skills.
We use a hash table cnt to store the count of each number.
When the add method is called, we increment the count of the number number.
When the find method is called, we iterate over the hash table cnt. For each key x, we check if value - x is also a key in the hash table cnt. If it is, we check if x is equal to value - x. If they are not equal, it means we have found a pair of numbers whose sum is value, and we return true. If they are equal, we check if the count of x is greater than 1. If it is, it means we have found a pair of numbers whose sum is value, and we return true. If it is less than or equal to 1, it means we have not found a pair of numbers whose sum is value, and we continue to iterate over the hash table cnt. If we have not found a pair after the iteration, we return false.
Time complexity:
add method is O(1).find method is O(n).Space complexity is O(n), where n is the size of the hash table cnt.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force List Scan | Add: O(1), Find: O(n^2) | O(n) | Small datasets or when simplicity matters more than performance |
| Hash Table Frequency Map | Add: O(1), Find: O(n) | O(n) | General case for streaming numbers with frequent find queries |
LeetCode 170. Two Sum III - Data structure design | Medium | Algorithm Explained | C++ • Cherry Coding [IIT-G] • 1,185 views views
Watch 9 more video solutions →Practice Two Sum III - Data structure design with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor