Problem statement

https://leetcode.com/problems/two-sum-iii-data-structure-design/

Solution

We can just keep our number in Counter. When we get new number just increase frequency. When we asked to find, iterate over num in our counter and if it is equal to half of value, check that frequency is at least 2. If it is not equal, check if we have corresponind number.

Complexity

Time complexity for add is $O(1)$, for find is $O(n)$. Space complexity of total data structure is $O(n)$`.

Code

class TwoSum:
    def __init__(self):
        self.cnt = Counter()
        
    def add(self, number: int) -> None:
        self.cnt[number] += 1
        
    def find(self, value: int) -> bool:
        for num in self.cnt:
            if num*2 == value:
                if self.cnt[num] >= 2: return True
            else:
                if value - num in self.cnt: return True
           
        return False

Remark

We can see that we have trade-off here between complexities of two operations. There is another solutions, where each time when we add new numbers, we add all pairs, so add will be $O(n)$ and find will be $O(1)$, total space complexity is $O(n^2)$. I am wondering if there is solution with say $O(\sqrt{n})$ complexity for both operations?