LeetCode 170: Two Sum III - Data Structure Design Solution in Python Explained
Designing a data structure to efficiently add numbers and find pairs that sum to a target might feel like crafting a dynamic lookup system, and LeetCode 170: Two Sum III - Data Structure Design is a medium-level challenge that makes it engaging! You need to implement a TwoSum
class with two methods: add(number)
to add a number to the data structure, and find(value)
to return whether there exist two numbers summing to value
. In this blog, we’ll solve it with Python, exploring two solutions—Hash Map with Frequency Tracking (our best solution) and Sorted List with Two Pointers (a practical alternative). With step-by-step examples, detailed code breakdowns, and tips, you’ll master this problem. Let’s build that structure!
Problem Statement
In LeetCode 170, you’re tasked with designing a TwoSum
class:
- add(number): Adds number to an internal data structure.
- find(value): Returns true if there exist two numbers in the structure summing to value, false otherwise.
The class will handle multiple calls, and numbers can repeat. This builds on LeetCode 167: Two Sum II - Input Array Is Sorted, extending to a dynamic design, and differs from majority finding like LeetCode 169: Majority Element.
Constraints
- -10^5 <= number <= 10^5
- -2 * 10^5 <= value <= 2 * 10^5
- Up to 10^4 calls to add and find
Example
Let’s see a case:
Input:
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output:
[null, null, null, null, true, false]
Explanation:
<ul>
<li>TwoSum(): Initialize empty structure.</li>
<li>add(1): [1]</li>
<li>add(3): [1,3]</li>
<li>add(5): [1,3,5]</li>
<li>find(4): 1+3=4, true</li>
<li>find(7): No pair sums to 7, false</li>
</ul>
This shows we’re dynamically managing numbers and checking sums.
Understanding the Problem
How do you solve LeetCode 170: Two Sum III - Data Structure Design in Python? We need a data structure supporting:
- add: Efficiently store numbers, allowing duplicates.
- find: Quickly check for pairs summing to a target.
For [1,3,5]
, find(4)
returns true
(1+3=4), find(7)
returns false
(no pair). Unlike Two Sum II’s sorted array, this is unsorted and dynamic, requiring a flexible approach. This isn’t a number-to-string task like LeetCode 168: Excel Sheet Column Title; it’s about data structure design. We’ll use:
1. Hash Map with Frequency Tracking: O(1) add, O(n) find, O(n) space—our best solution.
2. Sorted List with Two Pointers: O(n) add, O(n) find, O(n) space—an alternative.
Let’s dive into the best solution.
Best Solution: Hash Map with Frequency Tracking Approach
Explanation
Hash Map with Frequency Tracking uses a hash map to store number frequencies:
- add: Increment the count of number in the map (O(1)).
- find: For each number num, check if target - num exists:
- If target - num == num, ensure count ≥ 2.
- Otherwise, ensure target - num has count > 0.
- Return true if a valid pair is found.
This achieves O(1) time for add
, O(n) time for find
(n = unique numbers), and O(n) space, balancing efficiency and simplicity.
For [1,3,5]
:
- Map: {1:1, 3:1, 5:1{.
- find(4): 4-1=3, exists, return true.
- find(7): No pairs, return false.
Step-by-Step Example
Example: ["TwoSum", "add", "add", "add", "find", "find"], [[], [1], [3], [5], [4], [7]]
Goal: Return [null, null, null, null, true, false]
.
- Step 1: TwoSum().
- self.num_counts = {{.
- Step 2: add(1).
- num_counts = {1:1{.
- Step 3: add(3).
- num_counts = {1:1, 3:1{.
- Step 4: add(5).
- num_counts = {1:1, 3:1, 5:1{.
- Step 5: find(4).
- Check 1: 4-1=3, exists, return true.
- Step 6: find(7).
- 7-1=6, not found; 7-3=4, not found; 7-5=2, not found, return false.
- Finish: Output [null, null, null, null, true, false].
How the Code Works (Hash Map with Frequency Tracking) – Detailed Line-by-Line Explanation
Here’s the Python code with a thorough breakdown:
class TwoSum:
def __init__(self):
# Line 1: Initialize hash map
self.num_counts = {{
# Map for frequency (e.g., {{)
def add(self, number: int) -> None:
# Line 2: Add number to map
self.num_counts[number] = self.num_counts.get(number, 0) + 1
# Increment count (e.g., {1:1{, then {1:1, 3:1{)
def find(self, value: int) -> bool:
# Line 3: Check for pair summing to value
for num in self.num_counts:
# Iterate numbers (e.g., 1, 3, 5)
complement = value - num
# Target complement (e.g., 4-1=3)
# Line 4: Check if complement exists
if complement in self.num_counts:
# Complement found (e.g., 3 in map)
if complement != num:
# Different numbers (e.g., 1+3)
return True
elif self.num_counts[num] > 1:
# Same number, need count ≥ 2 (e.g., 2+2, if applicable)
return True
# Line 5: No pair found
return False
# e.g., false for 7
This detailed breakdown clarifies how the hash map approach efficiently supports two-sum operations.
Alternative: Sorted List with Two Pointers Approach
Explanation
Sorted List with Two Pointers maintains a sorted list:
- add: Insert number in sorted order (O(n)).
- find: Use two pointers (left, right) to find a pair summing to value (O(n)).
- Handle duplicates by tracking counts or allowing repeats in the list.
It’s a practical alternative, O(n) time for add
(insertion), O(n) time for find
, O(n) space, but slower for add
compared to hash map.
For [1,3,5]
:
- List: [1,3,5].
- find(4): 1+3=4, return true.
Step-by-Step Example (Alternative)
For the same example:
- TwoSum(): self.nums = [].
- add(1): [1].
- add(3): [1,3].
- add(5): [1,3,5].
- find(4): Left=1, Right=5, 1+3=4, true.
- find(7): No pair, false.
How the Code Works (Sorted List)
class TwoSumSorted:
def __init__(self):
self.nums = []
def add(self, number: int) -> None:
i = 0
while i < len(self.nums) and self.nums[i] <= number:
i += 1
self.nums.insert(i, number)
def find(self, value: int) -> bool:
left, right = 0, len(self.nums) - 1
while left < right:
curr_sum = self.nums[left] + self.nums[right]
if curr_sum == value:
return True
elif curr_sum < value:
left += 1
else:
right -= 1
return False
Complexity
- Hash Map with Frequency Tracking:
- Add Time: O(1) – hash map insertion.
- Find Time: O(n) – scan unique numbers.
- Space: O(n) – hash map.
- Sorted List with Two Pointers:
- Add Time: O(n) – insertion in sorted list.
- Find Time: O(n) – two-pointer scan.
- Space: O(n) – list.
Efficiency Notes
Hash Map with Frequency Tracking is the best solution with O(1) add
and O(n) find
, offering optimal efficiency for dynamic updates—Sorted List with Two Pointers uses O(n) for add
, making it slower for additions, though find
matches in time complexity, with O(n) space.
Key Insights
- Hash Map: Fast adds, frequency-aware.
- Sorted List: Sorted order for find.
- Duplicates: Handled differently.
Additional Example
For [1,1,2]
, find(2)
:
- Hash Map: {1:2, 2:1{, 1+1=2, true.
Edge Cases
- Empty: find(any) → false.
- Single: [1], find(2) → false.
- Duplicates: [1,1], find(2) → true.
Both solutions handle these well.
Final Thoughts
LeetCode 170: Two Sum III - Data Structure Design in Python is a practical design challenge. The Hash Map with Frequency Tracking solution excels with its efficiency and simplicity, while Sorted List with Two Pointers offers a sorted alternative. Want more? Try LeetCode 167: Two Sum II for a static version or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 170 on LeetCode with [1,3,5]
, find(4)
, aiming for true
—test your skills now!