# Minimizing the sum of differences in a pair [duplicate]

You have two arrays, a and b

Both contain n elements, all positive and distinct.

you have to create a pair, by taking one number from each array, such that the sum of the differences of the pairs are minimized.

for example, a = [1, 2, 3], b = [4, 5, 6]

one possible set of pairs = (1, 4), (2, 5), (3, 6)

sum of differences = |1 - 4| + |2 - 5| + |3 - 6| = 9

And now the sum of the differences has to be as small as possible

Desing an algorithm that those this is O(nlogn) time

So far, I have sorted both these arrays. I am unsure how to proceed now

• In fact, you have given the algorithm! Can you see it? Now the task for you is to verify why it works. Commented Jun 17, 2020 at 18:16
• is the algorithm simple solrt both arrays, and then use corresponding elements from each array as matching pairs? and is this the proof? cs.stackexchange.com/questions/21767/… Commented Jun 17, 2020 at 23:57
• Yes, you did it again. Commented Jun 18, 2020 at 1:39