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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What data structure does Breadth-first search typically uses to store intermediate states?

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.

Not Sure What to Study? Take the 2-min Quiz:

Which technique can we use to find the middle of a linked list?

Python Solution

1from collections import Counter
2
3class TwoSum:
4    def __init__(self):
5        # Initialize a counter to keep track of the number of occurrences of each number
6        self.num_counter = Counter()
7
8    def add(self, number: int) -> None:
9        # Increment the count for the added number.
10        self.num_counter[number] += 1
11
12    def find(self, value: int) -> bool:
13        # Check if there are any two numbers that add up to the given value.
14        for num, count in self.num_counter.items():
15            # The required partner number to reach the value
16            complement = value - num
17            # Check if the complement exists in the counter
18            if complement in self.num_counter:
19                # If the number and complement are the same, ensure there are at least two occurrences
20                if num != complement or count > 1:
21                    return True
22        # If no valid pair is found, return False
23        return False
24
25# Example usage:
26# two_sum_instance = TwoSum()
27# two_sum_instance.add(number)
28# result = two_sum_instance.find(value)
29

Java Solution

1// The TwoSum class provides a way to add numbers and find if there is a pair that sums up to a specific value.
2class TwoSum {
3    // A HashMap to store the numbers and their frequencies.
4    private Map<Integer, Integer> countMap = new HashMap<>();
5
6    // Constructor (empty since no initialization is needed here)
7    public TwoSum() {
8    }
9
10    // Adds the input number to the data structure.
11    public void add(int number) {
12        // Merges the current number into the map, incrementing its count if it already exists.
13        countMap.merge(number, 1, Integer::sum);
14    }
15
16    // Finds if there exists any pair of numbers which sum is equal to the value.
17    public boolean find(int value) {
18        // Iterates through the entries in our map
19        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
20            int currentKey = entry.getKey(); // The number in the pair we are currently considering.
21            int currentValue = entry.getValue(); // The count of how many times currentKey has been added.
22            int complement = value - currentKey; // The number that would complete the pair to equal 'value'.
23          
24            // Check if the complement exists in our map.
25            if (countMap.containsKey(complement)) {
26                // If currentKey and complement are the same number, we need at least two instances.
27                if (currentKey != complement || currentValue > 1) {
28                    return true; // Found a valid pair that sums up to the given value.
29                }
30            }
31        }
32        // If we haven't found any valid pair, return false.
33        return false;
34    }
35}
36
37// Example of how to use the TwoSum class:
38// TwoSum obj = new TwoSum();
39// obj.add(number);
40// boolean param2 = obj.find(value);
41

C++ Solution

1#include <unordered_map>
2using namespace std;
3
4// Class to store numbers and find if there are two numbers that add up to a specific value.
5class TwoSum {
6public:
7    // Constructor initializes the TwoSum object.
8    TwoSum() {
9    }
10
11    // Add the number to the internal data structure.
12    void add(int number) {
13        // Increment the count of this number in the hash map.
14        ++numCount[number];
15    }
16
17    // Find if there exists any pair of numbers which sum is equal to the value.
18    bool find(int value) {
19        // Iterate through the hash map using a range-based for loop.
20        for (const auto& numPair : numCount) {
21            const int& num = numPair.first;       // The current number from the hash map.
22            const int& frequency = numPair.second; // The frequency of the current number.
23
24            // Calculate the complement that we need to find.
25            long complement = (long)value - num;
26
27            // Check if the complement exists in the hash map.
28            if (numCount.count(complement)) {
29                // If the number and its complement are the same, check if the number occurs at least twice.
30                // Otherwise, we found a pair with the required sum.
31                if (num != complement || frequency > 1) {
32                    return true;
33                }
34            }
35        }
36
37        // If we reach here, no such pair exists.
38        return false;
39    }
40
41private:
42    // Hash map to store the count of each number added.
43    unordered_map<int, int> numCount;
44};
45
46// Usage example:
47// TwoSum* obj = new TwoSum();
48// obj->add(number);
49// bool param_2 = obj->find(value);
50

Typescript Solution

1// In a TypeScript environment, we do not often use global variables and functions,
2// as it is considered bad practice. However, here is how a similar functionality
3// could be implemented in TypeScript without a class.
4
5// An object to store the count of each number added.
6const numCount: Record<number, number> = {};
7
8// Adds the number to the internal data structure by incrementing its count.
9function addNumber(number: number): void {
10  if (numCount[number] !== undefined) {
11    numCount[number] += 1;
12  } else {
13    numCount[number] = 1;
14  }
15}
16
17// Finds if there exists any pair of numbers which sum is equal to the value.
18function find(value: number): boolean {
19  for (const num in numCount) {
20    // Parse the key as an integer since object keys are always strings.
21    const number = parseInt(num);
22
23    // Calculate the complement that is needed to find.
24    const complement = value - number;
25
26    // Check if the complement exists in the internal data structure.
27    if (numCount[complement] !== undefined) {
28      // If the number and its complement are the same, check if the number occurs at least twice.
29      // Otherwise, we have found a pair with the required sum.
30      if (number !== complement || numCount[number] > 1) {
31        return true;
32      }
33    }
34  }
35
36  // If we reach here, no such pair exists.
37  return false;
38}
39
40// Usage example (uncomment the following lines to use it in an environment that supports execution):
41// addNumber(1);
42// addNumber(3);
43// addNumber(5);
44// let result = find(4); // Should return true, because 1 + 3 = 4.
45// console.log(result);
46
Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?

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.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫