Skip to main content
Talentd

Two Sum III - Data structure design - Solution & Explanation

EasyPremiumFree on FleetCodeArrayHash TableTwo PointersDesign10 min readAsked at: Amazon, LinkedIn
Practice this problem

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 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 - 1
  • At most 104 calls will be made to add and find.

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.

Solution

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:

  • The time complexity of the add method is O(1).
  • The time complexity of the find method is O(n).

Space complexity is O(n), where n is the size of the hash table cnt.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force List ScanAdd: O(1), Find: O(n^2)O(n)Small datasets or when simplicity matters more than performance
Hash Table Frequency MapAdd: O(1), Find: O(n)O(n)General case for streaming numbers with frequent find queries

Video Solution

LeetCode 170. Two Sum III - Data structure design | Medium | Algorithm Explained | C++ • Cherry Coding [IIT-G] • 1,211 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Two Sum III - Data structure design easy or hard?
The problem is rated Easy on LeetCode but introduces a design twist compared to the classic Two Sum problem. Instead of solving a single query, you maintain a structure that supports repeated add and find operations. Understanding hash map complements makes the solution straightforward.
Two Sum III - Data structure design Python/Java solution
Most implementations store numbers in a dictionary or HashMap that tracks frequencies. The add method increments the count for a number, while the find method iterates through keys and checks whether the complement exists. The same logic works across Python, Java, C++, Go, and TypeScript with similar O(1) add and O(n) find complexity.
How to solve Two Sum III - Data structure design in O(n)?
Maintain a hash map that stores each number and its frequency. For a find(value) query, iterate through the keys and compute the complement value - num. Check if the complement exists in the map; if it is the same number, ensure the frequency is at least two. The scan across stored numbers leads to O(n) time per query.
What is the best approach for Two Sum III - Data structure design?
The hash table frequency map approach is the most efficient and commonly expected solution. Store each number with its occurrence count during the add operation. During find, iterate through the stored numbers and check whether the complement exists using O(1) hash lookups. This results in O(1) add time and O(n) find time.
Is Two Sum III - Data structure design asked at Google/Amazon/Meta?
Two Sum variations frequently appear in interviews at companies such as Amazon, Meta, and Google. This specific design variant tests whether you can adapt the classic Two Sum pattern into a reusable data structure with efficient operations. Interviewers often use it to evaluate understanding of hash tables and system design at a small scale.
What data structure is used in Two Sum III - Data structure design?
The core data structure is a hash table (hash map) that stores numbers and their frequencies. This enables constant-time insertion and fast complement lookups during the find operation. The problem is categorized under hash table and data structure design patterns.
What is the time complexity of Two Sum III - Data structure design?
Using the optimal hash table design, add(number) runs in O(1) time because it updates a frequency map entry. The find(value) operation runs in O(n) time since it iterates through stored numbers and performs constant-time complement lookups. Space complexity is O(n) to store the numbers and their counts.

Ready to solve this problem?

Practice Two Sum III - Data structure design with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Two Sum IV - Input is a BST