mediumClusteringML basics
K-Means Update Step
Run one iteration of k-means clustering: assign each point to its nearest centroid, then move every centroid to the mean of its points.
JavaScript or Python
K-means clustering repeats two steps until nothing changes: assign every point to its nearest centroid, then move each centroid to the mean of the points assigned to it. Implement one iteration.
Given points (a list of coordinate lists) and centroids (the current centres, same dimension), return the new centroids in the same order. Use squared Euclidean distance; if a point is equally close to two centroids, assign it to the one with the smaller index. A centroid with no points keeps its old position. Results are checked to six significant digits.
Examples
Example 1
Input: points = [[0, 0], [0, 2], [10, 10], [10, 12]], centroids = [[0, 1], [9, 9]] Output: [[0, 1], [10, 11]] Why: Two clear groups; each centroid moves to its group's mean
Example 2
Input: points = [[1, 1]], centroids = [[0, 0], [5, 5]] Output: [[1, 1], [5, 5]] Why: The second centroid gets no points and stays put
Constraints
0 <= points.length <= 10^41 <= centroids.length <= 501 <= dimension <= 50
Hints
Hint 1
For each point, find the centroid with the smallest squared distance; ties go to the smaller index.
Hint 2
Keep a running sum and count per centroid, then divide; an empty cluster keeps its centroid.
Solution
Show the solution (try it yourself first)
For each point, compute the squared distance to every centroid and keep the first minimum (a strict less-than comparison gives the smaller index on ties). Add the point to that centroid's running sum and count. Finally divide each sum by its count, keeping the old centroid when the count is zero.
def kmeans_step(points, centroids):
sums = [[0.0] * len(points[0]) for _ in centroids] if points else []
counts = [0] * len(centroids)
for p in points:
best, best_d = 0, None
for i, c in enumerate(centroids):
d = sum((a - b) ** 2 for a, b in zip(p, c))
if best_d is None or d < best_d:
best, best_d = i, d
counts[best] += 1
for j, v in enumerate(p):
sums[best][j] += v
return [[s / counts[i] for s in sums[i]] if counts[i] else list(c) for i, c in enumerate(centroids)]Complexity
Time O(n × k × d) per iteration for n points, k centroids and d dimensions; space O(k × d). Squared distance gives the same nearest centroid as distance and avoids square roots. Common follow-ups: k-means only finds a local optimum, so initialisation matters (k-means++), you choose k with the elbow method or silhouette score, and features need scaling because distances are involved.
Found a mistake in this problem, its tests or the solution?