K-Means Clustering

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:

• int location[n]: the feature locations of all the data points
• 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

Constraints

• 1 ≤ n ≤ 10⁵ <

Example 1

Input:

location = [4, 1, 6, 7, 2]
k = 2

Output:

2

Explanation: The maximum of all distances is 2.