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.
- Adding an integer to the collection.
- 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:
- If
x
equalsy
, then we need to have added this number at least twice forx + x = value
to be true. - If
x
does not equaly
, we simply need to check ify
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.
def __init__(self):
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
.
def add(self, number: int) -> None:
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
.
def find(self, value: int) -> bool:
for x, v in self.cnt.items():
y = value - x
if y in self.cnt:
if x != y or v > 1:
return True
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 fromy
andy
exists in the counter, a pair that sums up tovalue
was found. - If
x
equalsy
, we need to ensure thatx
was added at least twice (sincev
would be greater than 1 in such case) to say that we have a pair that adds up tovalue
.
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
twoSum = TwoSum()
Now let's add some numbers to the collection:
twoSum.add(1) twoSum.add(3) twoSum.add(5)
After these operations, the internal Counter
would look like this:
Counter({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:
twoSum.find(4)
The find
method will do the following:
- For each number
x
in theCounter
, it will calculatey = 4 - x
. - If
x
is 1, theny
will be 3, which is in theCounter
. Sincex
is not equal toy
, 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:
twoSum.add(1)
Now, the Counter
will be updated to:
Counter({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:
twoSum.find(2)
The method does the following:
- It calculates
y = 2 - x
for eachx
. - When
x
is 1,y
is also 1. - Since
x
equalsy
, we check the count ofx
in theCounter
; 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
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
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
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
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
Time and Space Complexity
add
Method:
- Time Complexity:
O(1)
on average for inserting thenumber
into theCounter
, though it could be in the worst caseO(n)
when there is a collision in the hashmap wheren
is the number of different elements added so far. - Space Complexity:
O(n)
wheren
is the number of different elements added to theCounter
since each new addition might be a unique number requiring additional space.
find
Method:
- Time Complexity:
O(n)
wheren
is the number of unique numbers added to theTwoSum
data structure. For each unique numberx
, thefind
method computesy
and checks ify
exists in theCounter
. The existence checky in self.cnt
takeO(1)
time on average. - Space Complexity:
O(1)
for this operation as it only stores the numbery
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.
In a binary min heap, the maximum element can be found in:
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Median of Data Stream Given a stream of numbers find the median number at any given time accurate to 1 decimal place Example add_number 1 add_number 2 add_number 3 get_median 2 0 add_number 4 get_median 2 5 Try it yourself Explanation Intuition Brute force way is to sort the entire list every time we get a new number This would be O N log N for each add_number operation One step up is to notice that the list is sorted before we add any new number to it So every
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!