Problem Description

You need to design a data structure that can accept a stream of integers and check if any pair of integers in the structure sum up to a given target value.

The data structure should support two operations:

1. Adding numbers: You can add integers one at a time to the data structure. The same number can be added multiple times.

2. Finding a pair sum: Given a target value, you need to check if there exist any two numbers in the current data structure that add up to this target. The two numbers can be:

   • Two different numbers (e.g., 3 + 5 = 8)
   • The same number used twice, but only if that number was added at least twice (e.g., if 4 was added twice, then 4 + 4 = 8 is valid)

The implementation uses a hash table to track the count of each number. When finding a pair:

• For each number x in the structure, it checks if value - x also exists
• If x and value - x are different numbers, a valid pair is found
• If x and value - x are the same number, it's only valid if that number appears at least twice

For example:

• After adding [1, 3, 5], find(4) returns true (1 + 3 = 4)
• After adding [3, 3], find(6) returns true (3 + 3 = 6)
• After adding [3], find(6) returns false (only one 3 available)

Intuition

The key insight is that for any target sum, we need to find two numbers a and b such that a + b = target. This means if we have a number a, we need to check if target - a exists in our data structure.

Instead of storing numbers in a simple list and checking all pairs (which would be inefficient), we can use a hash table to store both the numbers and their frequencies. Why frequencies? Because we need to handle the case where the same number might be used twice.

When we're looking for a pair that sums to value, for each number x we've stored, we calculate what its complement would be: y = value - x. Then we check:

1. Does y exist in our hash table? If not, x can't be part of a valid pair.

2. If y exists and x ≠ y, we've found two different numbers that sum to our target - this is always valid.

3. If y exists and x = y (meaning we need to use the same number twice), we need to check if we have at least 2 occurrences of that number. This is why we track counts rather than just presence.

The beauty of this approach is that the add operation becomes very simple - just increment a counter. The find operation, while needing to iterate through all unique numbers in the worst case, can immediately check for complements using hash table lookups in O(1) time per number.

This design choice optimizes for fast additions at the cost of slightly slower finds, which makes sense for a streaming data structure where we might add many numbers before querying for sums.

Solution Approach

The solution uses a hash table (Python's defaultdict) to maintain a count of each number that has been added to the data structure.

Initialization:

• Create an empty hash table cnt that will map each number to its frequency count
• Using defaultdict(int) ensures that accessing a non-existent key automatically initializes it to 0

Add Operation:

• When add(number) is called, simply increment the count for that number: self.cnt[number] += 1
• This is an O(1) operation since hash table insertion/update is constant time

Find Operation: The find(value) method iterates through each unique number in the hash table and checks if a valid pair exists:

1. For each number x and its count v in the hash table:

   • Calculate the complement: y = value - x
   • Check if y exists in the hash table

2. If y exists, we need to verify the pair is valid:

   • Case 1: Different numbers (x != y): If x and y are different numbers, we can always form a valid pair, so return true
   • Case 2: Same number (x == y): We need the same number twice, so check if the count v > 1. If yes, return true

3. If no valid pair is found after checking all numbers, return false

Example walkthrough:

• After adding [1, 3, 5], the hash table is {1: 1, 3: 1, 5: 1}
• Calling find(4):
  • For x = 1: y = 4 - 1 = 3, and 3 exists in hash table, 1 ≠ 3, so return true
• Calling find(2):
  • For x = 1: y = 2 - 1 = 1, 1 exists but count is 1 (not > 1), continue
  • For x = 3: y = 2 - 3 = -1, -1 doesn't exist, continue
  • For x = 5: y = 2 - 5 = -3, -3 doesn't exist, continue
  • No valid pair found, return false

Time Complexity:

• add: O(1) - single hash table update
• find: O(n) where n is the number of unique numbers in the hash table

Space Complexity: O(n) where n is the number of unique numbers stored

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Initial State: Empty data structure with hash table cnt = {}

Step 1: Add numbers

• add(3) → cnt = {3: 1}
• add(5) → cnt = {3: 1, 5: 1}
• add(3) → cnt = {3: 2, 5: 1} (note: 3 now has count 2)

Step 2: Find pair for target = 8

• find(8) → Need to find if any two numbers sum to 8
• Check each number x in hash table:
  • For x = 3:
    • Complement y = 8 - 3 = 5
    • Does 5 exist? Yes! (cnt[5] = 1)
    • Are they different numbers? Yes! (3 ≠ 5)
    • Valid pair found: 3 + 5 = 8 → Return true

Step 3: Find pair for target = 6

• find(6) → Need to find if any two numbers sum to 6
• Check each number x:
  • For x = 3:
    • Complement y = 6 - 3 = 3
    • Does 3 exist? Yes! (cnt[3] = 2)
    • Are they the same number? Yes! (3 = 3)
    • Do we have at least 2 occurrences? Yes! (cnt[3] = 2 > 1)
    • Valid pair found: 3 + 3 = 6 → Return true

Step 4: Find pair for target = 10

• find(10) → Need to find if any two numbers sum to 10
• Check each number x:
  • For x = 3:
    • Complement y = 10 - 3 = 7
    • Does 7 exist? No! → Continue
  • For x = 5:
    • Complement y = 10 - 5 = 5
    • Does 5 exist? Yes! (cnt[5] = 1)
    • Are they the same number? Yes! (5 = 5)
    • Do we have at least 2 occurrences? No! (cnt[5] = 1, not > 1)
    • Continue
  • No valid pair found → Return false

This example demonstrates all three scenarios: finding a pair with different numbers, finding a pair with the same number (when we have sufficient count), and not finding a valid pair.

Solution Implementation

Time and Space Complexity

Time Complexity:

• add(number): O(1) - Adding a number to the hash map (defaultdict) and incrementing its count is a constant time operation.
• find(value): O(n) - Where n is the number of unique numbers stored. In the worst case, we iterate through all key-value pairs in the dictionary to check if a valid pair exists that sums to the target value.

Space Complexity:

• O(n) - Where n is the number of unique numbers added. The space is used to store the hash map self.cnt, which contains at most n unique keys with their corresponding counts.

Analysis Details:

• The add method simply increments the count for a given number in the dictionary, which takes constant time due to hash map operations.
• The find method iterates through each unique number x in the dictionary and checks if y = value - x exists in the dictionary. The condition (x != y or v > 1) ensures that:
  • If x ≠ y, we need both numbers to exist in the dictionary
  • If x = y, we need at least two occurrences of that number (count > 1)
• The overall space is dominated by the storage of unique numbers and their counts in the hash map.

Common Pitfalls

1. Not Handling the Same Number Case Correctly

A frequent mistake is forgetting to check if we have enough occurrences when using the same number twice. For example:

Incorrect Implementation:

def find(self, value: int) -> bool:
    for num in self.count:
        complement = value - num
        if complement in self.count:  # Wrong! Doesn't check frequency
            return True
    return False

Problem: If we add only one 3 and call find(6), this would incorrectly return True because it finds 3 + 3 = 6, but we only have one 3 available.

Correct Solution: Always check frequency > 1 when num == complement:

if complement in self.count:
    if num != complement or self.count[num] > 1:
        return True

2. Using a Set Instead of Counting Frequencies

Some might try to optimize space by using a set to track unique numbers:

Incorrect Implementation:

def __init__(self):
    self.numbers = set()

def add(self, number: int) -> None:
    self.numbers.add(number)

def find(self, value: int) -> bool:
    for num in self.numbers:
        if value - num in self.numbers:
            return True
    return False

Problem: This fails when we need the same number twice. For example, after adding [3, 3], calling find(6) would return False because the set only stores one 3.

Correct Solution: Use a dictionary/hash map to track counts, not just presence.

3. Integer Overflow Concerns

In languages with fixed integer sizes, value - num could potentially overflow:

Potential Issue:

complement = value - num  # Could overflow in some languages

Solution: In Python this isn't an issue due to arbitrary precision integers, but in languages like Java or C++, consider using long integers or adding overflow checks:

// Java example with overflow consideration
long complement = (long)value - num;
if (complement > Integer.MAX_VALUE || complement < Integer.MIN_VALUE) {
    continue;
}

4. Modifying the Collection During Iteration

While not directly applicable to the given solution, a pitfall could arise if someone tries to optimize by removing elements during the find operation:

Incorrect Approach:

def find(self, value: int) -> bool:
    for num in list(self.count.keys()):  # Creating a copy to avoid RuntimeError
        complement = value - num
        if complement in self.count:
            # Don't modify self.count here!
            return True
    return False

Problem: The data structure should be persistent - find should not modify the stored numbers.

Correct Solution: Never modify the collection in the find method; it should be a read-only operation.