Min Cost to Connect All Points

The problem

You are given points, a list of [x, y] positions with whole-number coordinates. You may link any two points, and a link costs their Manhattan distance: how far apart the two x values are plus how far apart the two y values are. Return the smallest total cost of a set of links that connects all the points, so that every point can be reached from every other by following links. Two points at the same position cost 0 to link. If there are fewer than two points, return 0.

What to write

function solve(points: number[][]): number

Input
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]

Output
20

Input
points = [[3,12],[-2,5],[-4,1]]

Output
18

Constraints

0–200 two-dimensional integer points; coordinates within ±10,000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There are at most 200 points, so at most 19,900 pairs of points. Looking at every pair once or twice is cheap. Trying every set of links is hopeless. Also note that connecting n points takes only n - 1 links: any link beyond those joins two points that are connected already.

2. Hint 2: Ask a smaller question

   Take the three points of example 2. Their links cost 12, 6 and 18. Which two do you choose? Now imagine a fourth point far away from all three. Which one link would you add for it, and what did you have to compare to find that link?

3. Hint 3: Name the pattern

   The cheapest set of links that connects everything is called a minimum spanning tree: spanning because it reaches every point, tree because it has no closed loop. A request to connect everything at the lowest total cost is the signal. Growing the tree one point at a time, always by the cheapest link, is Prim's algorithm. Read the lesson on minimum spanning tree.

4. Hint 4: State the invariant

   For every point outside the tree, keep the cost of its cheapest link to any point inside: its cost to join. The point with the lowest cost to join goes in next. Once a point is in, only links from that new point can lower the costs of the others.

5. Hint 5: Sketch the pseudocode

   No points: return 0. Set every cost to infinity and the first point's cost to 0. Repeat once per point: among the unused points pick the one with the lowest cost, mark it used, add its cost to the total. Then lower each unused point's cost to its distance from the picked point if that is smaller. Return the total.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Grow a minimum spanning tree with Prim’s algorithm. Add the unused point with the cheapest connection, then update the costs for remaining points.

The slow way

Any two points can be linked, so 5 points have 10 possible links and 200 points have 19,900. You could try every set of links, keep the sets that connect all the points, and return the cheapest. It is correct, but each link is either in or out, so 10 links already make 1,024 sets, and every extra link doubles that.

The insight

Grow one connected group, the tree, from any point. Of all the links that lead from the tree to a point outside it, take the cheapest. That link is always safe: the outside has to be reached somehow, and no way of reaching it is cheaper. This is Prim's algorithm, and it builds a minimum spanning tree: the cheapest set of links that connects every point.

Step by step

1. With no points there is nothing to connect, so the cost is 0. The method starts the tree from the first point, and an empty list has no first point. The statement asks for 0 in that case, so it is answered before anything else.
2. Give every point a cost to join the tree; the first point costs 0. The tree is the set of points connected so far. A point's cost is its cheapest known link to the tree, and infinity means no link is known yet. The first point starts the tree, so it joins for free.
3. Find the point outside the tree that is cheapest to join. The cheapest link from the tree to the outside is always part of some cheapest way to connect everything, so taking it is never a mistake. One scan over the costs finds it.
4. Add that point to the tree and its cost to the total. Its cost is the price of the one link that ties it to the tree, so that is what the total grows by. The used mark keeps the point from being picked a second time.
5. A link from the new point may be cheaper: lower the outside costs. The tree has one new member, so every outside point has one new possible link to it. Keeping the smaller of the old cost and the new distance keeps each cost at the cheapest link to the tree.
6. Every point is in the tree: return the total. The loop runs once per point and each round adds exactly one point. After the last round all the points are connected, and the total is the sum of the links that were used.

The same numbered steps are the comments in each solution.

function solve(points) {
  // 1. With no points there is nothing to connect, so the cost is 0
  if (!points.length) return 0;
  // 2. Give every point a cost to join the tree; the first point costs 0
  const n = points.length,
    d = Array(n).fill(Infinity),
    used = Array(n).fill(false);
  d[0] = 0;
  let total = 0;
  for (let i = 0; i < n; i++) {
    // 3. Find the point outside the tree that is cheapest to join
    let u = -1;
    for (let j = 0; j < n; j++)
      if (!used[j] && (u < 0 || d[j] < d[u])) u = j;
    // 4. Add that point to the tree and its cost to the total
    used[u] = true;
    total += d[u];
    // 5. A link from the new point may be cheaper: lower the outside costs
    for (let j = 0; j < n; j++)
      if (!used[j])
        d[j] = Math.min(
          d[j],
          Math.abs(points[u][0] - points[j][0]) +
            Math.abs(points[u][1] - points[j][1]),
        );
  }
  // 6. Every point is in the tree: return the total
  return total;
}

function solve(points: number[][]): number {
  // 1. With no points there is nothing to connect, so the cost is 0
  if (!points.length) return 0;
  // 2. Give every point a cost to join the tree; the first point costs 0
  const n = points.length,
    d = Array(n).fill(Infinity),
    used = Array(n).fill(false);
  d[0] = 0;
  let total = 0;
  for (let i = 0; i < n; i++) {
    // 3. Find the point outside the tree that is cheapest to join
    let u = -1;
    for (let j = 0; j < n; j++)
      if (!used[j] && (u < 0 || d[j] < d[u])) u = j;
    // 4. Add that point to the tree and its cost to the total
    used[u] = true;
    total += d[u];
    // 5. A link from the new point may be cheaper: lower the outside costs
    for (let j = 0; j < n; j++)
      if (!used[j])
        d[j] = Math.min(
          d[j],
          Math.abs(points[u][0] - points[j][0]) +
            Math.abs(points[u][1] - points[j][1]),
        );
  }
  // 6. Every point is in the tree: return the total
  return total;
}

def solve(points):
    # 1. With no points there is nothing to connect, so the cost is 0
    if not points:
        return 0
    # 2. Give every point a cost to join the tree; the first point costs 0
    n = len(points)
    cost = [float("inf")] * n
    cost[0] = 0
    used = [False] * n
    total = 0
    for _ in range(n):
        # 3. Find the point outside the tree that is cheapest to join
        nearest = -1
        for j in range(n):
            if not used[j] and (nearest < 0 or cost[j] < cost[nearest]):
                nearest = j
        # 4. Add that point to the tree and its cost to the total
        used[nearest] = True
        total += cost[nearest]
        # 5. A link from the new point may be cheaper: lower the outside costs
        x1, y1 = points[nearest]
        for j, (x2, y2) in enumerate(points):
            if not used[j]:
                cost[j] = min(cost[j], abs(x1 - x2) + abs(y1 - y2))
    # 6. Every point is in the tree: return the total
    return total

Example 1, traced

Input
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]

Output
20

Why it works

Take any cheapest set of links. If it does not contain the link the method picks, it still joins that link's two ends by a route, and that route leaves the tree over some other link. Swap the two: everything stays connected, and the cost does not rise, because the picked link is the cheapest one leaving the tree. So every pick fits into some cheapest solution.

Time and space

Time O(n²), extra space O(n). There are n rounds, one per point. Each round makes two scans over the n points: one to find the cheapest and one to lower the costs. That is about n × n steps, O(n²). Only two lists of n entries are kept, costs and used marks: O(n) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Keep the lower of the old cost and the new distance. Overwriting the cost with the distance to the newest point forgets cheaper links from earlier points: example 1 then returns 25 instead of 20.
• Skip the points already in the tree when you look for the cheapest. Without that check the first point, whose cost is 0, is picked in every round, and example 1 returns 0.
• In Python the empty list needs its own check. Without it, setting the first point's cost to 0 raises an IndexError, because a list of no costs has no first slot. JavaScript returns 0 even without the check.

Pattern

Minimum spanning tree. Builds on Graph Valid Tree.

Keep going