Implement K-means clustering from scratch

Task

Implement K-means clustering from scratch (no ML libraries).

You are given a dataset of points:

• Input: an array X of shape (n, d) (n points, each d-dimensional)
• An integer k (number of clusters)
• max_iters and a convergence tolerance tol

Requirements

1. Initialize k centroids (you may choose a standard approach such as random points from X ).
2. Repeat until convergence or max_iters :
   • Assignment step: assign each point to its nearest centroid (e.g., Euclidean distance).
   • Update step: recompute each centroid as the mean of points assigned to it.
3. Handle the edge case where a cluster becomes empty.

Output

Return:

• centroids : array of shape (k, d)
• labels : array of length n with cluster indices 0..k-1

Follow-ups (discussion)

• Time complexity per iteration.
• How initialization affects convergence and quality (e.g., K-means++ idea).