FastPrepFastPrep
Problem Brief

Maximize Minimum Distance

FULLTIMEOA

Given a set of n distinct points on the x-axis, choose k of them such that the minimum distance between any two chosen points is as large as possible. Find this maximum possible minimum distance.

Function Description

Complete the function maximizeMinimumDistance in the editor below.

maximizeMinimumDistance has the following parameters:

  1. int x[n]: the x-coordinates of points
  2. int k the number of points to choose

Returns

int: the maximum possible minimum distance between any 2 of the chosen points

1Example 1

Input
x = [1, 4, 2, 9, 8], k = 3
Output
3
Explanation

In the optimal solution, one of the possible selection of points is {1, 4, 8}. Here,

  • The distance between 1 and 4 = abs(1 - 4) = 3
  • The distance between 1 and 8 = abs(1 - 8) = 7
  • The distance between 4 and 8 = abs(4 - 8) = 4

The minimum amongst them is 3, which is the maximum possible.

Constraints

Limits and guarantees your solution can rely on.

  • 2 ≤ n ≤ 10^5
  • 0 ≤ x[i] ≤ 10^9
  • 2 ≤ k ≤ n
  • All points are at distinct x-coordinates.
    • public int maximizeMinimumDistance(int[] x, int k) {
  // write your code here
}
    Input

    x

    [1, 4, 2, 9, 8]

    k

    3

    Output

    3

    Sign in to submit your solution.