Efficient data structure handling insert(number) and find(sum) returning pair a,b such that a + b = sum

Question

There are two operations as follows:

insert(num): insert num into the data structure.

find(sum): return a pair(a, b) such that a + b = sum, if no such pair exists return -1

How such data structure could be designed, possibly with find $\in o(N)$ and insert $\in o(\log N)$ operations?

Answer 1

It's unlikely that a data structure exists that supports both $insert(\cdot)$ and $find(\cdot)$ queries in $o(n/\log^2 n)$ time, since if it did, then we could use it to solve the 3SUM problem in $o(n^2/\log^2 n)$ time, beating the best known algorithm for this problem, which takes $O(n^2 (\log \log n)^{O(1)}/\log^2 n)$ time.

In 3SUM, we are asked to find 3 distinct elements that sum to zero in a list of distinct integers $x_1, \dots, x_n$. We can reduce this problem to your problem as follows:

1. For each $i$ from 1 to $n$:
   • Call $find(-x_i)$. If this succeeds, with return value $(x_a, x_b)$, then $x_a, x_b, x_i$ are all distinct and sum to zero: return TRUE.
   • Call $insert(x_i)$.
2. Return FALSE.

Answer 2

The best data structure I could come up with is the map (hashing based approach)

insert(num): O(1) for unordered/hash map

find(sum): O(N)

What I will do is that when I would get an insert query, I'll just increase the count of the num stored in my map by 1. And when I'll get the find query, I'll just iterate over the keys of the map and will try to find out if sum - key entry is present in the map or not, if present and key != sum/2 then directly return the pair or else if key == sum/2 and count of key > 1 then return the pair otherwise continue with my search over the keys.

And the c++ code would look like this:

void insert(int num) {
    my_map[num]++;
}

pair<int, int> find(int sum) {
    for (auto it = my_map.begin(); it != my_map.end(); it++) {
        int key = it->first;
        int res = sum - key;
        if (my_map.find(res) != my_map.end()) {
            if (2 * key == sum) {
                if (my_map[key] > 1) {
                    return {key, key};
                } else {
                    return {INT_MIN, INT_MIN};
                }
            } else if (my_map[res] > 0) {
                return {key, res};
            } else {
                return {INT_MIN, INT_MIN};
            }
        }
    }
    return {INT_MIN, INT_MIN};
}