CODEWITHSUNDEEP
algorithm
user3840069
user3840069

Reputation: 765

Take K elements and maximise the minimum distance

Given an array of N elements we can choose K positions out of N. But we need to choose K positions in such a way that if we take any of the two chosen positions say i and j than minimum difference (A[i]-A[j]) for all pair of i and j belonging to K choosen indexes should be as maximum as possible.

Example :

Let N=3 and array be = [3 9 6 11 15 20 23 ] and K=3

then here answer is 8 as one possible way is we can choose [3,11,23] or [3,15,23]

I just want to know can their be some greedy sort of approach for this problem ? Or a O(N) or O(N*log N) sort of approach ?

I know brute solution for it. But I don't think posting it here would be good idea as its very inefficient.

Constraints :

1 ≤ N ≤ 10^5
1 ≤ K ≤ 10^7

Upvotes: 3

Views: 1507

Answers (2)

Mohit Jain
Mohit Jain

Reputation: 30489

1. Sort the numbers
2. Pick first two numbers with maximum difference between them.
3. For i = 3 to k
   3.1 Pick the number that has maximum difference

Example

1. [3 9 6 11 15 20 23] -> [3 6 9 11 15 20 23]
2. [3 23]
3. Pick 11 or 15

Complexity = O(N log N) [(k+N) log N]

Upvotes: 1

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

You could do this using bisection on the value of the maximum difference.

First sort the elements in the array.

Then choose a value for the maximum difference, let's call it D.

Select the smallest entry in the array, then go through the array until we have reached a distance of D from this number, and select the next number. Repeat this until we have reached the end of the array.

This process will select a certain number of values from the array, which may be greater or fewer than K. You then use bisection on D to find the largest value of D that allows you to select at least K elements.

For example, with [3 6 9 11 15 20 23 ] we may first choose a difference of 5:

[3 6 9 11 15 20 23 ]
D=5: 3 9 11 20 => 4 chosen too high so increase D
D=10: 3 15 => 2 chosen too low so decrease D
D=8: 3 11 20 => 3 chosen

Upvotes: 1

Related Questions