Deterministic K-Means Assignments
Learn this problemProblem statement
Implement deterministic K-Means clustering for integer points. Use the first k points as the initial centroids, in that order.
Repeat these steps until no point changes its assigned cluster:
- Assign every point to the centroid with the smallest squared Euclidean distance. Break a tie by choosing the smaller cluster index.
- Replace each nonempty cluster's centroid with the coordinate-wise arithmetic mean of its assigned points. If a cluster is empty, keep its previous centroid.
Return an integer array whose value at index i is the zero-based cluster index assigned to points[i]. Implement the arithmetic and iteration directly; do not call a clustering library.
Function
clusterPoints(points: int[][], k: int) → int[]Examples
Example 1
points = [[0,0],[10,10],[1,0],[9,10]]k = 2return = [0,1,0,1]The first two points initialize the two centroids. The two points near the origin join cluster 0, and the two points near [10,10] join cluster 1. Recomputed centroids preserve those assignments.
Example 2
points = [[0],[4],[2]]k = 2return = [0,1,0]The point [2] is initially equally distant from centroids 0 and 4, so the smaller cluster index wins the tie.
Example 3
points = [[-5,2],[7,-1],[3,4]]k = 3return = [0,1,2]When every point initializes its own cluster, each point remains at distance zero from that centroid.
Constraints
1 <= points.length <= 2001 <= points[i].length <= 10- All points have the same dimension.
1 <= k <= min(points.length, 10)- The first
kpoints are pairwise distinct. -10000 <= points[i][j] <= 10000