Find Maximum Distance between two points

Question

Yesterday, I appeared in an interview. I was stuck in one of the question, and I am asking here the same.

There is an array given that shows points on x-axis, there are N points. and M coins also given.

Remember N >= M

You have to maximize the minimum distance between any two points.

Example: Array : 1 3 6 12
         3 coins are given.
         If you put coins on 1, 3, 6 points Then distance between coins are : 2, 3 
         So it gives 2 as answer 
         But we can improve further
         If we put coins at 1, 6, 12 points.
         Then distances are 5, 6
         So correct answer is : 5

Please help me because I am totally stuck in this question.

Answer 1

Here's my O(N²) approach to this. First, generate all possible distances;

int dist[1000000][3], ndist = 0;
for(int i = 0; i < n; i ++) {
    for(int j = i + 1; j < n; j ++) {
        dist[ndist][0] = abs(points[i] - points[j]);
        dist[ndist][1] = i; //save the first point
        dist[ndist][2] = j; //save the second point
    }
}

Now sort the distances in decreasing order:

sort(dist, dist + ndist, cmp);

Where cmp is:

bool cmp(int x[], int y[]) {
    return (x[0] > y[0]);
}

Sweep through the array, adding points as long as as you don't have m points chosen:

int chosen = 0;
int ans;
for(int i = 0; i < ndist; i ++) {
    int whatadd = (!visited[dist[i][1]]) + (!visited[dist[i][2]); //how many new points we'll get if we take this one
    if(chosen + whatadd > m) {
        break;
    }
    visited[dist[i][1]] = 1;
    visited[dist[i][2]] = 1;
    chosen += whatadd;
    ans = dist[i][0]; //ans is the last dist[i][0] chosen, since they're sorted in decreasing order
}
if(chosen != m) {
    //you need at most one extra point, choose the optimal available one
    //left as an exercise :)
}

I hope that helped!