2
$\begingroup$

If given two sets of integers how can I find an integer in the first set furthest away from all members of the second set. The distance of two integers is the absolute value of difference of the two integers. To clarify the question: if $a_i$ and $b_j$ are elements of the first and the second sets, I am trying to find $i$ such as $$\operatorname*{argmax}_{i} (\min_{j} |a_i - b_j|)$$

Thanks!

$\endgroup$
4
  • $\begingroup$ What did you try? $\endgroup$
    – Nathaniel
    Commented Feb 19 at 13:36
  • $\begingroup$ @Nathaniel I clarified the question. I tried bruteforce only. $\endgroup$
    – hovnatan
    Commented Feb 19 at 15:11
  • $\begingroup$ @hovnatan Thanks for clarifying the question, I've updated my answer $\endgroup$
    – SilvioM
    Commented Feb 19 at 16:24
  • $\begingroup$ what is a set? unordered list? sorted list? bitmap? generator function? $\endgroup$
    – Jasen
    Commented Feb 20 at 0:36

1 Answer 1

5
$\begingroup$

Since you now clarified your request, I give a new answer:

Assume your sets are $A$ and $B$, with $|A|=n$ and $|B|=m$. Let $k=\max(n,m)$. This is the procedure:

  1. Join the two sets $X=A\cup B$ in $\Theta(k)$ time.
  2. Sort $X$ in $\Theta((n+m)\log(n+m))=\Theta(k\log k)$ time.
  3. Scan the sorted set and, each time you encounter an element of $A$, it is sufficient to compute its distance from the previous element of $B$ and the next element of $B$ and take the minimum of the two distances. In this process, keep track of the maximum of these minimum distances. This can be easily done in $\Theta(k)$.

So, the overall time complexity is $\Theta(k\log k)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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