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!

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

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.