1
$\begingroup$

I have two arrays that both contain $n$ elements (positive, non zero, not negative)
$\{x_1\dots x_n\}$
$\{y_1\dots y_n\}$

I want to pair them up optimally, one from each array, so that the pairs come out as even as possible, when paired up optimally. I want the difference between the highest sum of pair values and the lowest such sum to be as small as possible.
I know there are brute force ways but they take $O(n^2)$ time, and I want the time complexity to be low, say $O(n^{1.5})$ or lower.

My approach is to sort one of the arrays in ascending order, and one in descending order and pair them up.
How would I go about making sure they are actually paired optimally so that difference between the smallest sum and the highest sum among pairs is as small as possible?

Improve this question
$\endgroup$
3
  • $\begingroup$ I don't understand what you mean by "the highest value pair" or "the lowest value pair" or the difference between them. Can you edit your question to clarify the objective function you are trying to minimize? Can you tell us where you encountered this task or the motivation? Can you show us your algorithm that uses $O(n^2)$ time? $\endgroup$
    – D.W. ♦
    Commented Feb 14, 2023 at 19:02
  • $\begingroup$ For example by adding two for loops, the time complexity would take O(n^2) time, the highest value pair would be the pair that has the highest value after they have been paired "optimally" ( as even as possible) if that clarifies it! $\endgroup$
    – Ally Zane
    Commented Feb 15, 2023 at 9:35
  • $\begingroup$ This was cross-posted. stackoverflow.com/a/75497214/585411 has my answer. $\endgroup$
    – btilly
    Commented Feb 19, 2023 at 0:15

2 Answers 2

Reset to default
2
$\begingroup$

my approach is to sort one of the arrays in ascending order, and one in descending order and pair them up

Yes, that's optimal.

You pair the smallest x-value $x$ with the largest y-value $Y$. Suppose that's a mistake, i.e., you end up with a solution worse than some optimal better solution which pairs $x$ with some other $y \le Y$ (and thus pairs $Y$ with some other $X \ge x$). So that optimal solution has sums $x+y$ and $X+Y$. Now modify that optimal solution to use $x+Y$ and $X+y$ instead. We have $x+y \le x+Y,X+y \le X+Y$, so replacing $x+y$ and $X+Y$ with $x+Y$ and $X+y$ doesn't extend the range and thus the solution stays optimal. Meaning there is an optimal solution that does pair $x$ and $Y$. You're good.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is sketchy in just arguing that at least one optimal solution will pair the minimum of one array with the maximum of the other. It does not explicitly claim taking these items out, there is a like problem of size $n-1$ (a solution to which will be a solution to the original problem when expanded by the pair argued about). $\endgroup$
    – greybeard
    Commented Feb 19, 2023 at 12:55
  • $\begingroup$ @greybeard In my opinion, that's just standard boilerplate common to greedy algorithm proofs and not interesting. I might include it if I were still at university and wanted to ensure getting full points, but I don't consider it necessary here. $\endgroup$
    – Kelly Bundy
    Commented Feb 19, 2023 at 13:14
  • $\begingroup$ You may well be right - I'm decades from being used to proofs. My off-hand characterisation as sketchy has originated over at SO. $\endgroup$
    – greybeard
    Commented Feb 19, 2023 at 13:18
0
$\begingroup$

If your goal is to minimize the maximum absolute difference of each pair, I suggest trying to explore greedy algorithms. In particular, suppose the arrays are presented in sorted order, and suppose for the moment that there are no duplicates, so $x_1 < x_2 < \cdots$ and $y_1 < y_2 < \cdots$. Suppose $x_1 < y_1$. What can you say about which element $x_1$ should be paired with? Can you make a greedy choice and proceed, and prove that this will give an optimal algorithm?

Improve this answer
$\endgroup$
1
  • $\begingroup$ Hmm, I would say that after adding them lets say n=4 and we have some array x=[x1,x2,x3,x4] combined with y=[y1,y2,y3,y4] and the optimal combination (adding x+y) o=[5,4,3,1] the highest value 5 minus lowest value 1, to be as small as possible. Does that mean that the combination beforehand has so be the minimum absolute difference of the pairs? $\endgroup$
    – Ally Zane
    Commented Feb 15, 2023 at 11:16

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.