learn deep. ship safe.Practice testsFollow ByteMunSubscribe

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^4
  • 1 <= centroids.length <= 50
  • 1 <= 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?

Written by Published Tests checked by Deepak
Case 1Input: [[0,0],[0,2],[10,10],[10,12]], [[0,1],[9,9]]Expected: [[0,1],[10,11]]
Case 2Input: [[1,1]], [[0,0],[5,5]]Expected: [[1,1],[5,5]]

Run checks these 2 samples. Submit checks all 6 tests, including hidden ones.

  1. Maximum Subarray SumArrays · Dynamic programming
    medium
  2. Longest Substring Without RepeatsStrings · Sliding window · Hash map
    medium
  3. Group AnagramsStrings · Hash map · Sorting
    medium
  4. Merge Overlapping IntervalsArrays · Sorting · Intervals
    medium