subset with elements that are furthest apart from each other

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.

Example:

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

UPDATE : meaning of furthest apart : the difference b/w any two elements in the subset is mimimum .

1 Like

What do you mean “furthest apart”? Maximizing the minimum of differences between any 2 values in the set?

In that case, you could bin-search the answer. If you think that the answer is at least D, you can start with the first element and always greedily pick the smallest element that’s >= D + the last picked element. If there are >= K such elements, it can be done (if there are more, you just pick the last K); otherwise, it obviously isn’t possible for this D. If you sort this array beforehand, you can do this in just one pass for a fixed D. And since it’s obviously always possible for any D <= answer and impossible for D > answer, binsearch works. Time: O(N log A_max).

3 Likes

what do u mean by furthest apart from each other? is it the indexes or the difference b/w any two elements?

the_c0der: Is the trolling (not specifying to which possibility yes) intentional? :smiley:

There are 4 possibilities, actually: of indexes or values, and maximum difference or minimum difference. But the ones with maximum difference are trivial, and what’s the point in values if we’re only interested in indexes?

2 Likes

@xellos0 : please see update

I believe you meant “the minimum difference between any two elements is maximum” :smiley:

In that case, see my answer below.