Two Sum III - Data structure design - Video Solutions
LeetCode 170. Two Sum III - Data structure design | Medium | Algorithm Explained | C++
Two Sum III - Data structure design - Video Solution
Watch 10 video solutions for Two Sum III - Data structure design, a easy level problem involving Array, Hash Table, Two Pointers. This walkthrough by Cherry Coding [IIT-G] has 1,211 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 theTwoSumobject, with an empty array initially.void add(int number)Addsnumberto the data structure.boolean find(int value)Returnstrueif there exists any pair of numbers whose sum is equal tovalue, otherwise, it returnsfalse.
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 - 1- At most
104calls will be made toaddandfind.
Approach Overview
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.
Complexity Analysis
| 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 |