Two Sum III - Data structure design - Solution & Explanation

Problem Overview: Design a data structure that supports two operations: add(number) to store a number from a data stream, and find(value) to check if any pair of stored numbers sums to the given value. The challenge is balancing fast insertions with efficient pair-sum checks.

Approach 1: Store Numbers in List (Brute Force) (add: O(1), find: O(n^2), space: O(n))

Keep every number in a list. The add operation simply appends to the list in constant time. For find, iterate through every pair of elements and check whether their sum equals the target value. This brute force approach works for small inputs but quickly becomes slow because pair checking requires two nested loops. It demonstrates the core idea of pair searching but is rarely acceptable in interviews.

Approach 2: Hash Set Check Per Query (add: O(1), find: O(n), space: O(n))

Store all numbers in a list or set. During find, iterate through the numbers and compute the complement target - num. Track visited values in a temporary hash set to detect if the complement already appeared in the iteration. Each lookup is O(1) using a hash table, reducing the query to linear time. This approach avoids checking every pair explicitly and mirrors the classic Two Sum optimization.

Approach 3: Hash Map Frequency Counter (add: O(1), find: O(n), space: O(n))

Maintain a hash map where the key is the number and the value is its frequency. The add operation increments the count in constant time. For find, iterate through each unique number and compute the complement. If the complement exists in the map, a valid pair exists. A special case occurs when num == complement; the frequency must be at least two. This design is clean, avoids duplicates issues, and is the most common solution in data structure design interviews.

Approach 4: Precompute Pair Sums (add: O(n), find: O(1), space: O(n^2))

Maintain a set containing sums of every pair inserted so far. When add is called, compute sums between the new number and all previously stored numbers, inserting them into the set. The find operation becomes a constant-time lookup in the set. This approach is useful when queries are extremely frequent compared to insertions, such as certain data stream scenarios. The downside is quadratic memory growth as more numbers are added.

Recommended for interviews: The hash map frequency approach is what interviewers usually expect. It keeps add O(1), handles duplicates correctly, and keeps the design simple. Mentioning the brute force first shows understanding of the baseline, then moving to the hash map demonstrates optimization and practical design thinking.