Problem
K-means finds groups in unlabeled data. Starting from the given centroids, repeat iterations times:
- Assign: put each point in the cluster of its nearest centroid (Euclidean distance). If two centroids are equally close, choose the one with the smaller index.
- Update: move each centroid to the average of the points assigned to it. A centroid with no points stays where it is.
Implement k_means(points, centroids, iterations).
Input
points: The data points, each a list of coordinates.
centroids: The k starting centroids, with the same number of coordinates.
iterations: How many assign-and-update rounds to run.
Output
Return the final centroids in their original order.
Constraints
1 ≤ number of points ≤ 1,000, 1 ≤ k ≤ 20, 1 ≤ dimensions ≤ 10
0 ≤ iterations ≤ 100
-1,000 ≤ each coordinate ≤ 1,000
Examples
Input:
points = [
[1.0, 1.0],
[1.5, 2.0],
[8.0, 8.0],
[9.0, 8.5]
]
centroids = [
[0.0, 0.0],
[10.0, 10.0]
]
iterations = 1
Expected output:
expected = [
[1.25, 1.5],
[8.5, 8.25]
]Input:
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{1.5, 2.0},
{8.0, 8.0},
{9.0, 8.5}
};
std::vector<std::vector<double>> centroids = {
{0.0, 0.0},
{10.0, 10.0}
};
long long iterations = 1;
Expected output:
std::vector<std::vector<double>> expected = {
{1.25, 1.5},
{8.5, 8.25}
};Input:
double[][] points = new double[][] {
new double[] {1.0, 1.0},
new double[] {1.5, 2.0},
new double[] {8.0, 8.0},
new double[] {9.0, 8.5}
};
double[][] centroids = new double[][] {
new double[] {0.0, 0.0},
new double[] {10.0, 10.0}
};
long iterations = 1;
Expected output:
double[][] expected = new double[][] {
new double[] {1.25, 1.5},
new double[] {8.5, 8.25}
};Explanation
The first two points are nearer to (0, 0) and the last two nearer to (10, 10). The new centroids are the averages: ((1 + 1.5) / 2, (1 + 2) / 2) = (1.25, 1.5) and ((8 + 9) / 2, (8 + 8.5) / 2) = (8.5, 8.25).
Input:
points = [
[0.0],
[1.0],
[10.0]
]
centroids = [
[0.0],
[100.0]
]
iterations = 2
Expected output:
expected = [
[3.666667],
[100.0]
]Input:
std::vector<std::vector<double>> points = {
{0.0},
{1.0},
{10.0}
};
std::vector<std::vector<double>> centroids = {
{0.0},
{100.0}
};
long long iterations = 2;
Expected output:
std::vector<std::vector<double>> expected = {
{3.666667},
{100.0}
};Input:
double[][] points = new double[][] {
new double[] {0.0},
new double[] {1.0},
new double[] {10.0}
};
double[][] centroids = new double[][] {
new double[] {0.0},
new double[] {100.0}
};
long iterations = 2;
Expected output:
double[][] expected = new double[][] {
new double[] {3.666667},
new double[] {100.0}
};Explanation
Round 1: (100) is far from every point, so all three points join centroid 1, which moves to (0 + 1 + 10) / 3 ≈ 3.666667; centroid 2 gets no points and stays at 100. Round 2 assigns the same way, so the result is [[3.666667], [100]].
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
Alternate between assigning every point to its nearest centroid and recomputing each centroid from its assigned points.
Hint 2
When distances tie, choose the centroid with the smaller index, and keep an empty centroid unchanged.
Hint 3
Average each coordinate independently, and repeat the full assign-update cycle exactly the requested number of times.
Expected complexity
O(iterations × n × k × d) time, O(n + k d) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.