Wiring the Campsites

MediumgreedyAlso known as Min Cost to Connect All Points

A campground is adding electric hook-ups. Each pitch has grid coordinates [x, y] on the site map. Cable has to run along the gravel paths, which go only north-south and east-west, so a cable between two pitches costs |x1 - x2| + |y1 - y2| metres.

Power can pass through a pitch to reach the next one, so every pitch just needs to be connected to the rest by some chain of cables. The manager wants the least total cable that does it.

Your task

Write minCable(pitches). Each entry is [x, y]. You may lay a cable between any two pitches, at a cost equal to their distance along the paths, |x1 - x2| + |y1 - y2|. Return the smallest total cost so that every pitch is connected to every other, directly or through other pitches.

One pitch needs no cable: return 0. Two pitches can share the same coordinates; joining them costs 0.

minCable(pitches: int[][]) → int

Examples

Example 1

Input

pitches = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]

Output

Why

Lay [0,0]–[2,2] (4), [2,2]–[5,2] (3), [5,2]–[7,0] (4) and [2,2]–[3,10] (9). Total 20. The cable to [3,10] is the expensive one, and 9 is the cheapest cable that reaches it: every other one costs at least 10.

Example 2

Input

pitches = [[0, 0], [1, 0], [10, 0], [11, 0]]

Output

Why

Two pairs, each with a 1-metre cable. Linking each pitch to its own nearest neighbor gives just those two cables, which leaves two separate groups. One more cable is needed to bridge the gap, and the cheapest is [1,0]–[10,0] at 9. Total 1 + 1 + 9 = 11.

Constraints

1 ≤ pitches.length ≤ 1,000
-1,000,000 ≤ x, y ≤ 1,000,000

Start with brute force

List all n(n - 1)/2 possible cables and try every subset of n - 1 of them that connects everything, keeping the cheapest.

With just 20 pitches there are 190 cables and about 6 × 10²⁵ ways to pick 19 of them. Greedy choices are provably safe here, so you never need to search. Kruskal's algorithm (sort all cables, add each one that joins two different groups) also works, but with 1,000 pitches it has to sort about 500,000 cables first.

Hints

0 of 4 shown

Hint 1
Look at the second example. If you connect each pitch to its nearest neighbor, is everything connected? What is still missing?
Hint 2
Any cheapest plan uses exactly n - 1 cables and has no loops: a loop always contains a cable you could remove and stay connected. So you are choosing a tree.
Hint 3
Grow the network from one pitch. At every moment you have a connected group and the pitches outside it. Which single cable is always safe to add next?
Hint 4
Use Prim's algorithm. Keep, for every pitch outside the group, the cheapest cable to any pitch inside it. Repeatedly add the outside pitch with the smallest such cost, add that cost to the total, then update the other outside pitches using the distance to the newly added one. With all pairs possible, a plain O(n²) scan is simplest; no heap needed.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

The cheapest way to connect everything is a minimum spanning tree. Prim's algorithm builds it by growing one group: the cheapest cable that leaves the group is always part of some cheapest plan, so take it, and repeat.

Trace the first example. Pitches: A [0,0], B [2,2], C [3,10], D [5,2], E [7,0]. Start with A in the group.

Cheapest cable from A to each outside pitch: B 4, C 13, D 7, E 7. Take B (4). Total 4.
Update with distances from B: C becomes 9, D becomes 3, E stays 7. Take D (3). Total 7.
Update with distances from D: C stays 9, E becomes 4. Take E (4). Total 11.
Update with distances from E: C stays 9 (E to C is 14). Take C (9). Total 20.

Each pitch keeps only one number: its cheapest cable into the group so far. When a new pitch joins, that number can only go down, and only the new pitch's distances need checking. That is why one O(n) update per step is enough.

A heap version of Prim's is the usual choice for sparse graphs. Here every pair of pitches can be linked, so the graph is dense, and the plain array scan is both simpler and faster.

Reference solution

function minCable(pitches) {
  const n = pitches.length;
  const inTree = new Array(n).fill(false);
  const cheapest = new Array(n).fill(Infinity); // best cable into the tree
  cheapest[0] = 0;
  let total = 0;
  for (let added = 0; added < n; added++) {
    let pick = -1;
    for (let i = 0; i < n; i++) {
      if (!inTree[i] && (pick === -1 || cheapest[i] < cheapest[pick])) pick = i;
    }
    inTree[pick] = true;
    total += cheapest[pick];
    const [px, py] = pitches[pick];
    for (let i = 0; i < n; i++) {
      if (inTree[i]) continue;
      const d = Math.abs(px - pitches[i][0]) + Math.abs(py - pitches[i][1]);
      if (d < cheapest[i]) cheapest[i] = d;
    }
  }
  return total;
}

def min_cable(pitches):
    n = len(pitches)
    in_tree = [False] * n
    cheapest = [float('inf')] * n  # best cable into the tree
    cheapest[0] = 0
    total = 0
    for _ in range(n):
        pick = -1
        for i in range(n):
            if not in_tree[i] and (pick == -1 or cheapest[i] < cheapest[pick]):
                pick = i
        in_tree[pick] = True
        total += cheapest[pick]
        px, py = pitches[pick]
        for i in range(n):
            if not in_tree[i]:
                d = abs(px - pitches[i][0]) + abs(py - pitches[i][1])
                if d < cheapest[i]:
                    cheapest[i] = d
    return total

TimeO(n²)n rounds, each scanning all pitches once to pick and once to update.

SpaceO(n)Two arrays of length n; the cables are never stored.

Learn the idea: Minimum Spanning Trees Greedy Algorithms Union-Find

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code