Two Sum Iii Data Structure Design - Leetcode Solution

Problem:

Design a data structure that accepts a set of integers and supports two methods:

1. add(number): Add an integer number to the data structure.
2. find(value): Find if there exists any pair of integers which sum is equal to the value.

Example:

add(1); 
add(3); 
add(5);
find(4) -> true
find(7) -> false

Solution:

One solution is to use a hash table to keep track of the numbers and their frequency. To add a number, simply increment its frequency in the hash table. To find a pair of integers that sum to a target value, iterate through the hash table and check if the complement of each number exists in the hash table. If it does, return true. If no such pair exists, return false.

The time complexity of adding a number is O(1) on average and O(n) in the worst case (if there are many collisions in the hash table). The time complexity of finding a pair of integers is O(n), since we need to iterate through the hash table once.

Here's the implementation in Python:

class TwoSum:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nums = {}

    def add(self, number: int) -> None:
        """
        Add the number to an internal data structure..
        """
        self.nums[number] = self.nums.get(number, 0) + 1

    def find(self, value: int) -> bool:
        """
        Find if there exists any pair of numbers which sum is equal to the value.
        """
        for num in self.nums:
            complement = value - num
            if complement in self.nums and (complement != num or self.nums[num] > 1):
                return True
        return False

Note that we need to check if complement != num or self.nums[num] > 1 to handle the case where the target value is equal to twice a number (e.g., find(6) when we have added 3 twice). If we didn't do this check, the method would return True even though there is no pair of distinct integers that sum to the target value.

1