1
$\begingroup$

I have a question that is essentially asking me to find the minimum absolute value between the difference of pairs in two arrays.

If I have an array $A = [1, 3, 2, 4]$ and $B=[9,6,8,10]$, Then it would be best to sort both arrays A and B so that $A=[1,2,3,4]$ and $B=[6,8,9,10]$, then iterate through both arrays and calculate the absolute value of the difference between the numbers at each point. This will give you the minimum.

What I can't put into mathematical words is why. I can intuitively understand it, but I can't put it into words. Can someone explain why this is, mathematically?

$\endgroup$
1
$\begingroup$

From the ordering of the arrays you can't really deduce something about the ordering of their differences (in general), so why do you first sort the arrays?

However, consider $C=\{1,2,3,4\}$ and $D=\{9,6,8,10\}$ as sets. You want to find $\min\{|c-d|:c\in C, d\in D\}$. You can do that by first calculating all differences $\{|c-d|:c\in C, d\in D\}$ and then select the minimum.

Now what you algorithm does is the following: Given a particular order of $C$ and $D$ (your sorted arrays), it "builds" the set $\{|c-d|:c\in C, d\in D\}$ step by step (basically constructing sets $S_1$, $S_2$ etc. until $S_m=\{|c-d|:c\in C, d\in D\}$ for some $m$, where $S_i$ and $S_{i+1}$ only differ by one element) and at each step looks what the minimum of the newly constructed set is. But your algorithm is intelligent enough not to construct the sets explicitly in memory, but concentrates on the minimas. It uses that $\min (S_i\cup\{j\})=\min\{j,\min S_i\}$, so the algorithm only carries the current minimum $\min S_i$ and the index $i$ to know what it has checked and what still needs checking. You see that in the end, it gets $\min S_m = \min\{|c-d|:c\in C, d\in D\}$ (what we looked for).

You didn't specify in which way the arrays are iterated through, so I kept it general, but possibly you iterate through all elements of $A$ and in that loop through all elements of $B$. In that case, the number of sets implicitly constructed in the "background" (but not explicitly in the algorithm) is $m=4\cdot 4=16$.

$\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.