K-Means Delivery Zones
Problem statement
DoorDash wants to split customer locations into k delivery zones. Each location is a point, and every point has the same number of integer coordinates. Implement k-means clustering from scratch. Follow the rules below exactly, so that everyone gets the same answer.
The squared distance between two points is the sum of the squared differences of their coordinates. For example, between (1, 2) and (4, 6) it is 3^2 + 4^2 = 25.
- There are
kcenters, numbered0tok - 1. Centerjstarts atpoints[j]. Two centers may start at the same place. - Run
maxIterationsrounds. Each round has two steps:- Assign: every point joins the center with the smallest squared distance to it. If several centers are equally close, the point joins the one with the smallest number.
- Update: every center moves to the mean (average) of the points that joined it, one coordinate at a time. The mean can be a fraction, such as
6.5. A center that no point joined stays where it is.
- Return an array
answerwhereanswer[i]is the center thatpoints[i]joined in the last round.
If a round gives exactly the same assignment as the round before, nothing can change anymore, so you may stop early. The answer stays the same.
Function
kMeans(points: int[][], k: int, maxIterations: int) → int[]Examples
Example 1
points = [[1],[2],[10],[11],[3]]k = 2maxIterations = 10return = [0,0,1,1,0]The centers start at the first two points: center 0 is at 1 and center 1 is at 2.
Round 1: point 1 is closest to center 0. Points 2, 10, 11 and 3 are closest to center 1 (for 3, the squared distances are 4 and 1). Center 1 moves to (2 + 10 + 11 + 3) / 4 = 6.5.
Round 2: points 1, 2 and 3 are now closer to center 0 (for 3: 4 versus 12.25), and 10 and 11 stay with center 1. The centers move to (1 + 2 + 3) / 3 = 2 and (10 + 11) / 2 = 10.5.
Round 3 gives the same assignment, so nothing changes anymore. The answer is [0, 0, 1, 1, 0].
Example 2
points = [[0,0],[0,0],[4,0],[2,0]]k = 2maxIterations = 5return = [1,1,0,0]Both centers start at (0, 0), because the first two points are the same.
Round 1: every point is equally close to both centers, so every point joins center 0, the smaller index. Center 0 moves to (1.5, 0). Center 1 got no points, so it stays at (0, 0).
Round 2: the two points at (0, 0) are now closer to center 1 (squared distance 0 versus 2.25). (4, 0) and (2, 0) stay with center 0 (6.25 versus 16, and 0.25 versus 4). Center 0 moves to (3, 0).
Round 3 gives the same assignment. The answer is [1, 1, 0, 0].
Example 3
points = [[0,0],[1,1],[5,5],[6,6],[2,2]]k = 2maxIterations = 2return = [0,0,1,1,1]The centers start at (0, 0) and (1, 1).
Round 1: only (0, 0) joins center 0. The other four points are closer to center 1; for (2, 2) the squared distances are 8 and 2. Center 1 moves to (3.5, 3.5).
Round 2: (1, 1) switches to center 0 (2 versus 12.5). (2, 2) stays with center 1 (8 versus 4.5). The assignment is [0, 0, 1, 1, 1].
That was round maxIterations = 2, so we stop and return [0, 0, 1, 1, 1]. (A third round would move (2, 2) to center 0.)
Constraints
1 <= points.length <= 3001 <= points[i].length <= 4- All points have the same number of coordinates.
-10^4 <= points[i][j] <= 10^41 <= k <= 8k <= points.length1 <= maxIterations <= 50- In every test, if two centers are not exactly equally close to a point, their squared distances differ by more than
10^-3. So ordinarydoublemath gives the exact answer.