170. Two Sum III - Data structure design

Problem Description

The problem requires the design of a data structure to manage a stream of integers and provides two functionalities.

1. Adding an integer to the collection.
2. Querying to find out if there are any two distinct integers already in the collection that add up to a specified target sum.

This data structure should efficiently support the insertion of numbers and the checking for the existence of a pair of numbers that meet the target sum condition.

Intuition

The intuition behind the solution is to use a data structure that allows us to efficiently check for the existence of a specific number. A hash map or hash table comes to mind because it provides constant time complexity, O(1), lookup on average for insertions and searches.

Since we're dealing with pairs and their potential sums, when a query is made to find a pair that sums up to a value value, we can traverse each number x that has been added to the data structure and calculate its complement y (where y = value - x). Then, we can check if the complement y exists in the hash map. There are a couple of cases to consider:

1. If x equals y, then we need to have added this number at least twice for x + x = value to be true.
2. If x does not equal y, we simply need to check if y is present in the hash map.

We use a Counter to keep track of the occurrences of each number, which is essentially a specialized hash map that maps each number to the count of its occurrences. This allows us to handle both above-mentioned cases effectively.

By using this approach, we ensure that the add operation is done in constant time, while the find operation is done in O(n) time, where n is the number of unique numbers added to the data structure so far. This is an acceptable trade-off for the problem.

Learn more about Two Pointers and Data Stream patterns.

Solution Approach

The given solution makes use of the Counter class from Python's collections module. The Counter is a subclass of the dictionary that is designed to count hashable objects. It is an unordered collection where elements are stored as dictionary keys and their counts are stored as dictionary values.

Initialization:

The __init__ method initializes the TwoSum class.

1def __init__(self):
2    self.cnt = Counter()

Here, an instance of Counter is created to keep track of how many times each number has been added to the data structure. This tracking is crucial for handling cases when the same number might be a part of the solution pair.

The add Method:

The add method takes an integer number and increments its count in the Counter.

1def add(self, number: int) -> None:
2    self.cnt[number] += 1

Whenever a number is added, the Counter is updated so that the find method can reference the correct frequencies of the numbers.

The find Method:

The find method takes an integer value and tries to find if there are two distinct integers in the data structure that add up to value.

1def find(self, value: int) -> bool:
2    for x, v in self.cnt.items():
3        y = value - x
4        if y in self.cnt:
5            if x != y or v > 1:
6                return True
7    return False

In this method, we iterate through each item in the Counter. For each number x, we calculate its complement y (value - x). We then check if y exists in the Counter:

• If x is different from y and y exists in the counter, a pair that sums up to value was found.
• If x equals y, we need to ensure that x was added at least twice (since v would be greater than 1 in such case) to say that we have a pair that adds up to value.

If no such pair is found during the iteration, the method returns False.

To summarize, this solution utilizes a hash-based data structure (Counter) for efficient lookups and count tracking to help identify if there exists a pair that sums up to the target value. The add method operates in O(1) time complexity, and the find method operates in O(n) time complexity, making the solution suitable for problems involving integer pairs with a specific sum.

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Imagine we initialize the data structure, and no numbers have been added yet. The Counter is therefore empty:

1twoSum = TwoSum()

Now let's add some numbers to the collection:

1twoSum.add(1)
2twoSum.add(3)
3twoSum.add(5)

After these operations, the internal Counter would look like this:

1Counter({1: 1, 3: 1, 5: 1})

The counts reflect that each of the numbers 1, 3, and 5 has been added once.

Now, if we want to check if there exist any two distinct numbers that add up to 4, we call:

1twoSum.find(4)

The find method will do the following:

• For each number x in the Counter, it will calculate y = 4 - x.
• If x is 1, then y will be 3, which is in the Counter. Since x is not equal to y, this is a valid pair that adds up to 4.
• Since a valid pair is found, the method will return True.

Now let's add the number 1 once more to the collection:

1twoSum.add(1)

Now, the Counter will be updated to:

1Counter({1: 2, 3: 1, 5: 1})

The count for the number 1 is now 2 because we have added it twice.

If we now call find with a target sum of 2:

1twoSum.find(2)

The method does the following:

• It calculates y = 2 - x for each x.
• When x is 1, y is also 1.
• Since x equals y, we check the count of x in the Counter; it is 2, which means number 1 was added more than once.
• Hence we have two distinct occurrences of the number 1, and they add up to 2.
• The method returns True, indicating that there exists a pair that sums up to the target value.

The example demonstrates how the add method updates the Counter, and how the find method iterates through the available numbers, checking for the existence of a valid pair whose sum matches the target value.

Solution Implementation

Time and Space Complexity

add Method:

• Time Complexity: O(1) on average for inserting the number into the Counter, though it could be in the worst case O(n) when there is a collision in the hashmap where n is the number of different elements added so far.
• Space Complexity: O(n) where n is the number of different elements added to the Counter since each new addition might be a unique number requiring additional space.

find Method:

• Time Complexity: O(n) where n is the number of unique numbers added to the TwoSum data structure. For each unique number x, the find method computes y and checks if y exists in the Counter. The existence check y in self.cnt take O(1) time on average.
• Space Complexity: O(1) for this operation as it only stores the number y in memory and doesn't use any additional space that depends on the input size.

Learn more about how to find time and space complexity quickly using problem constraints.