LeetCode 170: Two Sum III - Data Structure Design Solution in Python Explained

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!