Solution: Two Sum III - Data structure design

Let's solve the Two Sum III - Data structure design problem using the Custom Data Structures pattern.

We'll cover the following

Statement

Design a data structure that takes in a stream of numbers and can check if any two numbers add up to a specific value.

Implement the TwoSum class with the following constructor and methods:

  • Constructor: Sets up the TwoSum object with an empty list at the start.

  • void add(int number): Adds a new number to the list.

  • boolean find(int value): Returns TRUE if any two numbers in the list add up to the given value. If not, it returns FALSE.

Constraints:

  • −105≤-10^5 \leqnumber ≤105\leq 10^5

  • −231≤-2^{31} \leqvalue ≤231−1\leq 2^{31} -1

  • At most, 10410^4 calls will be made to add and find methods.

Solution

The algorithm uses a custom data structure to solve this problem efficiently. The idea is to use a hash map to store the numbers and their frequencies as we iterate over the array. This custom data structure will allow us to quickly look up and manage the frequencies of the numbers. Using the frequency data, we can quickly identify whether the required pair of numbers or sufficient occurrences of a single number are present to achieve the target sum.

We will iterate over the numbers array and put each number in the hash map with the frequency of 11 or increase their frequency by 11 if that number is already in the hash map. Next, we will check if any two numbers or two frequencies of a single number can sum up to the target number. To accomplish that, we will loop over all the keys of the hash map and check if the key’s difference (target - key) exists as another key or if at least two frequencies of the difference exist.

The algorithm to solve this problem is as follows:

  • Create a class and initialize an instance of the hash map in its constructor. Moreover, implement two methods in the class: add(number) and find(target).

  • add(number) method. If a number is not already in the hash map, put that number in the hash map as a key and 11 as a value. If the number is already in the hash map, increase that number's value (frequency) by 11.

  • find(target) method. Iterate over the keys of the hash map. For each key, calculate the difference as target - key.

    • If the difference is not equal to the key, check if the hash map has another key equal to the difference; if so, it means we have found two numbers equal to target and will return true.

    • If the difference is equal to the key, check if the frequency of key is at least two. If so, we have found two numbers equal to the target and will return true.

    • In either case, if no two numbers sum up to target, we will return false.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.