For each element A[i] of array A, find the closest j such that A[j] > A[i]

Question

Hi everyone.

---

Given : An array A[1..n] of real numbers.

Goal : An array D[1..n] such that

D[i] = min{ distance(i,j) : A[j] > A[i] }

or some default value (like 0) when there is no higher-valued element. I would really like to use Euclidean distance here.

Example :

A = [-1.35, 3.03, 0.73, -0.06, 0.71, -0.21, -0.12, 1.49, 1.41, 1.42]
D = [1, 0, 1, 1, 2, 1, 1, 6, 1, 2]

---

Is there any way to beat the obvious O(n^2) solution? The only progress I've made so far is that D[i] = 1 whenever A[i] is not a local maxima. I've been thinking a lot and have come up with NOTHING. I hope to eventually extend this to 2D (so A and D are matrices).

Answer 1

So I've puzzled on this a bit but I haven't come up with anything better that works. A few ideas:

• Augment the array with extra information that can be gained in O(n) time or better. e.g., add indices, difference between neighbors, etc.
• Would sorting (O(n(log n)) help in any way?
• Seems like dynamic programming could be helpful here, if you can figure out a way to solve for each element based on the solution for its neighbors (augmenting the answers with information like the j for each A[i] instead of just the distance maybe).

Answer 2

Sort the array from highest to lowest element. If I understand your problem correctly, this gives you the answer immediately, since the closest bigger element to any element in the original list is the one before it. This way you don't even need to create the D[] array, since computation of its contents can be done using the array A[] exclusively. The first element in the sorted A[] array does not have a bigger friend so the answer for it would be your default valye ( 0 perhaps?). Extending the algorithm for matrices might be easy (depends on how you "look" at the matrix) - just use a mapping function which sort of transofrms the matrix into a 1D array.