2
$\begingroup$

This is an algorithm design question which often appears in exams in a course that I take in the university . Suppose I have an array $A\in\mathbb{R}$ of size $n$ . I am required to find the $\frac{n}{\log n}$ largest differences $|a_i-a_j|$ for every $\,\,i\neq j\,\,$ ($i,j\in [1,n]$) . I must do this in linear time , that is my algorithm should run in $\, O(n)$ .
Now the initial idea for the solution would be to use the Select algorithm to find the $\frac{n}{\log n}$ and $n-\frac{n}{\log n}$ order statistics , then scan the array again and split it to groups $A_1$ in which every member is smaller than the $\frac{n}{\log n}$ order statistic, and $A_2$ in which every member is greater than the $n-\frac{n}{\log n}$ order statistic . Each such group is of size $\frac{n}{\log n}$ so sorting them will take linear time (I won't go into the calculation of this).
Now here's my problem . As mentioned I'm at the stage where I have 2 arrays containing $\frac{n}{\log n}$ smallest and $\frac{n}{\log n}$ greatest elements of array $A$ sorted in two arrays . I can't think of an algorithm to find the greatest $\frac{n}{\log n}$ differences other than knowing that the min value of $A_1$ and the max value of $A_2$ will form the first greatest difference .Help?

$\endgroup$
4
  • $\begingroup$ What are the possibilities for the second greatest difference? $\endgroup$
    – user14972
    Jan 29, 2014 at 16:33
  • $\begingroup$ I guess the max value and second order statistic or the order statistic prior to the max with the min value . These are all possibilities for perhaps the 2 first differences , however trying all possibilities might result in $O(n^2)$ unless there is a sophisticated way to scan through all differences in linear time which is what I really look for . $\endgroup$
    – MLech2013
    Jan 29, 2014 at 18:14
  • $\begingroup$ For simplicity, let $A_0, A_1, A_2, \cdots$ be the largest values in decreasing order and $B_0, B_1, B_2, \cdots$ be the smallest values in increasing order. Anyways, you know $A_0 - B_0$ was the largest. Suppose that $A_0 - B_1$ was the second largest difference. Now what are the possibilities for the third largest difference? I think you can just write out all of the differences in order of magnitude; note you can afford to do $O(\log n)$ work per step, if you need to. $\endgroup$
    – user14972
    Jan 29, 2014 at 18:38
  • $\begingroup$ Sorry , I'm not following you . Can you be a little more specific? $\endgroup$
    – MLech2013
    Jan 30, 2014 at 12:13

0

You must log in to answer this question.

Browse other questions tagged .