# Calculating the kth largest distance among $n$ points on a number line in $O(n\log n)$?

I have got some difficulties to solve this algorithm problem.

I have been given a set of n points on a number line. Those points are not sorted in the set. For any two points $(a, b)$ in the set, their distance is calculated as $|a-b|$. Now I need to calculated the kth largest among all possible distances of the n points in $O(n \log n)$ time using a randomized algorithm and a deterministic algorithm respectively.

To solve this problem, I begin with sorting the n points in $O(n \log n)$ time. I noticed that this problem it is similar to the quick select for the kth largest of the array. The naive approach is to calculate all possible distances and do quick select. But this takes $O(n^2)$ running time. It seems that I have to run the quick select with only necessary distances calculated. Now I have to do two things recursively:

1. partition all distances with a randomly chosen pivot, and
2. find out the numbers of distances on each side to determine which part for recursion.

There would be $O(n \log n)$ steps for the recursion. So, I have to do the two things above in $O(n)$ time. And I have difficulties with that.

• If you can do it using a deterministic algorithm, then you can use the same algorithm as a randomized algorithms that happens to not use any randomness. Feb 17, 2017 at 8:14
• Since the requirement is O (n log n), and you can sort the data in O (n log n), you can assume the data is sorted. Feb 17, 2017 at 10:43
• @gnasher729 I have considered that as well, but how to proceed from that? Feb 17, 2017 at 16:34
• You say that you need "find out the numbers of distances on each side". OK. So what approaches have you considered, for doing that? What have you tried? What prevents you from making progress? Can you articulate exactly what that problem statement is, in precise self-contained terms (what are the inputs? what are the outputs?), and then think about how you might try to calculate it? Suppose you wanted to know how many pairs a,b there are such that $|a-b| \le 0.0001$. Could you think of a way to do that? What about the number such that $|a-b| \le 1$?
– D.W.
Feb 17, 2017 at 16:45
• If the array is sorted, then the largest distance is from the first to the last element. Feb 17, 2017 at 20:18

Given some pivot $K$, you can count the pairs with differences above it in $O(n)$, whether you use a random pivot or binary search.

The pairs form a kind of uneven grid in the plane, and you can search diagonally along the line $y = K+x$ to find the border between $x_j - x_i \le K$ and $x_j - x_i \gt K$ in $O(n)$ as follows (Bresenham's Line Drawing Algorithm):

1. Start at the y axis and find minimum $j$ so that $x_j - x_0 > K$

2. $Count = n-j+1$

3. For $i = 1$ to $n-1$ do

While $x_j - x_i < K$, $j = j+1$

If $j=n$ break

$Count = Count + n - j + 1$

(There are some adjustments for when K is larger than the range, but the main idea is here.)

Basically you move right and then slide $j$ up until you cross the line, then add all the entries above that point to the count. As you continue right you're always at or above the $j$ you used in the previous column, so you do $O(n)$ pair tests for the whole scan.

Given are numbers $x_1$ to $x_n$. We assume they are sorted in non-decreasing order (since they can be sorted in O (n log n)). We assume that the distance d (i, j) between $x_i$ and $x_j$ is calculated in constant time as $x_j - x_i$, if j ≥ i, with fixed precision. When we are looking for "the k-th largest distance", we look for a pair (i, j), i ≤ j, such that d (i', j') ≥ d (i, j) for exactly k pairs (i', j'), i' ≤ j'. The solution may be not unique. Assume 1 ≤ k ≤ n (n+1) / 2, otherwise there is no solution.

Subproblem: Given d ≥ 0, find how many pairs (i, j), i ≤ j, there are with d (i, j) ≥ d (we will want to find d such that this number is k). This can be done in linear time: For every i, 1 ≤ i ≤ n, let $j_i$ be the smallest j, i ≤ j ≤ n, such that d (i, j) ≥ d, or $j_i = n + 1$ if no such j exists. We get the number of pairs by adding $n - j_i + 1$ for 1 ≤ i ≤ n.

To find $j_i$, we let $j_i = 1$ if i = 1, and $j_i = max (i, j_{i-1})$ if i > 1. Then as long as $j_i ≤ n$ and $d (i, j_i) < d$ we increase $j_i$ by 1. This is all done in linear time, because we don't increase the various values of $j_i$ more than n times in total.

Main problem: We know that 0 ≤ d (i, j) ≤ d (1, n). So we just perform a binary search to find d, 0 ≤ d ≤ d (1, n) such that exactly k values d (i, j) are ≤ d: Start with low = 0, high = d (1, n). If high = 0 then all distances are 0, and any (i, j), i ≤ j, is a solution.

Otherwise repeat as long as there are possible values between low and high: Pick mid between low and high with about equal numbers of values low < mid and mid < high (if the distances are floating-point numbers then mid is usually not (low + high) / 2). Find how many pairs (i, j) there are with d (i, j) ≥ mid. If that number is ≥ k then let high = mid, otherwise let low = mid.

Eventually low and high are consecutive possible values. If there are less than k pairs d (i, j) ≥ high then let d = low, otherwise d = hi. Use the (subproblem) algorithm above to find the pairs d (i, j) ≥ d; that algorithm will also find (i, j) with d (i, j) = d, and that's the solution.

• I don't understand how you propose to find how many distances are $\le d$. Can you elaborate? What does $d_i$ represent? Does it represent the $i$th distance, or the $i$th element of the array? If the latter, it might be clearer to use a different notation (e.g., $x_i$ or $x[i]$).
– D.W.
Feb 17, 2017 at 21:14