FastPrepFastPrep
Problem Brief

K-Means Clustering

OA

Source image will be included in next update :)

In a k-means clustering problem, a dataset contains n data points, where nth data point is represented by the feature vector location[i]. The goal is to create k clusters, where the cluster centers or the cluster centroids can be placed at any point in the feature space. The overall quality of the clustering is measured by the maximum distance between any data point and its nearest cluster center.

The best possible quality is achieved by optimally placing the cluster centers to minimize this maximum distance. Determine this maximum distance between any data point and its nearest cluster center.

Note: The distance between two feature points x and y is defined as |x-y|, where |x| denotes the absolute value of x.

Function Description

Complete the function getMaximumDistance in the editor below.

getMaximumDistance takes the following parameters:

  1. int location[n]: the feature locations of all the data points
  2. int k: the number of clusters

Returns

int: the maximum distance between any data point and its nearest cluster center by optimally placing the k clusters

1Example 1

Input
location = [4, 1, 6, 7, 2], k = 2
Output
2
Explanation
The maximum of all distances is 2.

Constraints

Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ 10^5
  • 1 ≤ k ≤ n
  • 1 ≤ location[i] ≤ 10^9
public int getMaximumDistance(int[] location, int k) {
  // write your code here
}
Input

location

[4, 1, 6, 7, 2]

k

2

Output

2

Sign in to submit your solution.