170. Two Sum III - Data structure design
Model: qwen2.5-coder:14b
Topics: Hash Table,Design
FAANG asked: 0
Acceptance rate: 35.0%
Problem Breakdown
The problem requires designing a data structure that can efficiently handle two operations: adding an integer to the data structure and checking if there exists any pair of integers in the data structure that sum up to a given value. The inputs are a series of add operations with integers and find operations with target sums. The outputs for find operations are boolean values indicating whether such a pair exists.
Inputs:
add(int number): Adds an integer to the data structure.find(int value): Checks if any two numbers in the data structure sum up to the given value.
Outputs:
- For
find, returntrueif there is at least one pair of integers that sum to the target value, otherwise returnfalse.
Implicit Constraints and Edge Cases:
- The data structure should handle a large number of operations efficiently.
- Duplicates are allowed, meaning the same integer can be added multiple times.
- Negative numbers are possible.
- Overflow conditions need to be considered for the sum operation.
Intuition
A brute-force approach would involve storing all numbers in an array and checking each pair during the find operation. This approach has a time complexity of O(n^2) for the find operation, which is inefficient given the constraints.
The key insight is to use a hash table (dictionary in Python) to store the frequency of each number added. During the find operation, we can check if there exists another number that complements the current number to reach the target sum. This reduces the time complexity for the find operation to O(n), where n is the number of unique numbers stored.
Approach
-
Data Structure Choice:
- Use a dictionary (
self.num_counts) to store each unique number as a key and its frequency as the value.
- Use a dictionary (
-
Initialization:
- Initialize an empty dictionary in the constructor.
-
Add Operation:
- When adding a number, increment its count in the dictionary.
- If the number is not already present, add it with a count of 1.
-
Find Operation:
- For each unique number in the dictionary:
- Calculate the complement needed to reach the target sum (
complement = value - number). - Check if the complement exists in the dictionary.
- If the complement is the same as the current number, ensure there are at least two occurrences of this number.
- Calculate the complement needed to reach the target sum (
- Return
trueif such a pair is found; otherwise, returnfalse.
- For each unique number in the dictionary:
Complexity Analysis
-
Time Complexity:
add(int number): O(1), as dictionary operations (insert and update) are average O(1).find(int value): O(n), where n is the number of unique numbers stored in the dictionary.
-
Space Complexity:
- O(n), where n is the number of unique numbers added to the data structure.
Solution
class TwoSum:
def __init__(self):
# Initialize an empty dictionary to store the frequency of each number
self.num_counts = {}
def add(self, number: int) -> None:
# Add the number to the dictionary or increment its count if it already exists
if number in self.num_counts:
self.num_counts[number] += 1
else:
self.num_counts[number] = 1
def find(self, value: int) -> bool:
# Iterate through each unique number in the dictionary
for number in self.num_counts:
complement = value - number
# Check if the complement exists in the dictionary
if complement in self.num_counts:
# If the complement is the same as the current number, ensure there are at least two occurrences
if complement == number and self.num_counts[number] > 1:
return True
elif complement != number:
return True
# Return false if no valid pair is found
return False
Edge Cases Handled
- Empty Input: The data structure starts empty, and
findoperations will correctly returnfalse. - Duplicates: The dictionary stores the frequency of each number, allowing duplicates to be handled.
- Negative Numbers: The solution works with negative numbers as they are valid inputs.
- Overflow: The problem constraints ensure that overflow conditions do not occur within the given range.