Maximum average distance between two numbers across multiple arrays

user_6831212 0
Viewed 276

Let's say you have k arrays of size N, each containing unique values from 1 to N.

How would you find the two numbers that are on average the furthest away from each other?

For example, given the arrays:

[1,4,2,3]
[4,2,3,1]
[2,3,4,1]

Then the answer would be item 1 and 2, because they are of distance 2 apart in the first two arrays, and 3 numbers apart in the last one.

I am aware of an O(kN^2) solution (by measuring the distance between each pair of numbers for each of the k arrays), but is there a better solution?

I want to implement such an algorithm in C++, but any description of a solution would be helpful.

arrays algorithm performance
2 Answers

After a linear-time transformation indexing the numbers, this problem boils down to computing the diameter of a set of points with respect to L1 distance. Unfortunately this problem is subject to the curse of dimensionality.

Given

    1 2 3 4
1: [1,4,2,3]
2: [4,2,3,1]
3: [2,3,4,1]

we compute

    1 2 3
1: [1,4,4]
2: [3,2,1]
3: [4,3,2]
4: [2,1,3]

and then the L1 distance between 1 and 2 is |1-3| + |4-2| + |4-1| = 8, which is their average distance (in problem terms) times k = 3.

That being said, you can apply an approximate nearest neighbor algorithm using the input above as the database and the image of each point in the database under N+1-v as a query.

user_21446690

I've a suggestion for the best case. You can follow an heuristical approach.

For instance, You know that if N=4, N-1=3 will be the maximum distance and 1 will be the minimum. The mean distance is 10/6=1,66667 (sums of distances among pairs within array / number of pairs within an array).

Then, you know that if two numbers are on the edges for k/2 arrays (most of the times), it is already on the average top (>= 2 of distance), even if they're just 1 distance apart in the other k/2 arrays. That could be a solution for a best case in O(2k) = O(k).

user_76295600
Related