Find subset with elements that are furthest apart from eachother

Question

I have an interview question that I can't seem to figure out. Given an array of size N, find the subset of size k such that the elements in the subset are the furthest apart from each other. In other words, maximize the minimum pairwise distance between the elements.

Example:

Array = [1,2,6,10]
k = 3

answer = [1,6,10]

The bruteforce way requires finding all subsets of size k which is exponential in runtime.

One idea I had was to take values evenly spaced from the array. What I mean by this is

1. Take the 1st and last element
2. find the difference between them (in this case 10-1) and divide that by k ((10-1)/3=3)
3. move 2 pointers inward from both ends, picking out elements that are +/- 3 from your previous pick. So in this case, you start from 1 and 10 and find the closest elements to 4 and 7. That would be 6.

This is based on the intuition that the elements should be as evenly spread as possible. I have no idea how to prove it works/doesn't work. If anyone knows how or has a better algorithm please do share. Thanks!

Answer 1

This can be solved in polynomial time using DP.

The first step is, as you mentioned, sort the list A. Let X[i,j] be the solution for selecting j elements from first i elements A.

Now, X[i+1, j+1] = max( min( X[k,j], A[i+1]-A[k] ) ) over k<=i.

I will leave initialization step and memorization of subset step for you to work on.

In your example (1,2,6,10) it works the following way:

    1    2   6   10
1   -    -   -    -
2   -    1   5    9
3   -    -   1    4
4   -    -   -    1

Answer 2

The basic idea is right, I think. You should start by sorting the array, then take the first and the last elements, then determine the rest.

I cannot think of a polynomial algorithm to solve this, so I would suggest one of the two options.

One is to use a search algorithm, branch-and-bound style, since you have a nice heuristic at hand: the upper bound for any solution is the minimum size of the gap between the elements picked so far, so the first guess (evenly spaced cells, as you suggested) can give you a good baseline, which will help prune most of the branches right away. This will work fine for smaller values of k, although the worst case performance is O(N^k).

The other option is to start with the same baseline, calculate the minimum pairwise distance for it and then try to improve it. Say you have a subset with minimum distance of 10, now try to get one with 11. This can be easily done by a greedy algorithm -- pick the first item in the sorted sequence such that the distance between it and the previous item is bigger-or-equal to the distance you want. If you succeed, try increasing further, if you fail -- there is no such subset.

The latter solution can be faster when the array is large and k is relatively large as well, but the elements in the array are relatively small. If they are bound by some value M, this algorithm will take O(N*M) time, or, with a small improvement, O(N*log(M)), where N is the size of the array.

As Evgeny Kluev suggests in his answer, there is also a good upper bound on the maximum pairwise distance, which can be used in either one of these algorithms. So the complexity of the latter is actually O(N*log(M/k)).