3
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Jan 26 at 20:49
  • $\begingroup$ Note how "better than O(_)" doesn't make any sense. That's like saying "colder than at most 10°". $\endgroup$ – Raphael Jan 26 at 20:51
  • 1
    $\begingroup$ Finally, you are asking two very different questions. Which is the important one for you, any data structure that does the job or a lower bound? Do you already have a solution with the bounds you give in the second question? $\endgroup$ – Raphael Jan 26 at 20:52
  • 1
    $\begingroup$ Please provide a simple non-trivial example of the problem. $\endgroup$ – Apass.Jack Jan 27 at 3:52
  • $\begingroup$ @Evil: Small $o$? I'd feel hard pressed to find a representation where expected/amortised insertion time is dominated by $\log N$ as well as finds by $N$. $\endgroup$ – greybeard Jan 28 at 4:37
4
$\begingroup$

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.
$\endgroup$
0
$\begingroup$

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};
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.