FastPrep
Problem · Binary Search

Maximize Minimum Distance

Learn this problem
● MediumIBM logoIBMFULLTIMEOA
See IBM hiring insights

Problem statement

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

maximizeMinimumDistance(x: int[], k: int) → int

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

Examples

Example 1

x = [1, 4, 2, 9, 8]k = 3return = 3

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

  • 2 ≤ n ≤ 10^5
  • 0 ≤ x[i] ≤ 10^9
  • 2 ≤ k ≤ n
  • All points are at distinct x-coordinates.

    • More IBM problems

    drafts saved locally
    public int maximizeMinimumDistance(int[] x, int k) {
  // write your code here
}
    x[1, 4, 2, 9, 8]
    k3
    expected3
    checking account