← Weighted Undirected Graph → Minimum Spanning Tree

Min Cost to Connect All Points

Medium
Solve it on LeetCode ↗

The problem

Given points on a plane, the cost to connect two points is their Manhattan distance. Return the minimum total cost to make all points connected.

Stuck? Reveal hints one at a time

How to approach it

  1. 1Maintain minDist[i]: cheapest cost to attach point i to the tree built so far. Start with point 0 in the tree.
  2. 2Repeat n−1 times: pick the un-added point with the smallest minDist and add it, paying that cost.
  3. 3After adding point u, update every remaining point’s minDist against dist(u, point).
  4. 4Sum the n−1 attachment costs.

Key insight

On a complete graph, heap-based Prim is O(n² log n) — worse than the simple O(n²) array scan. Density decides the implementation.

The solution

Watch out for

  • Kruskal here means materializing ~n²/2 edges and sorting them — fine for n=1000 but strictly more work.
  • minDist must track distance to the TREE, not to point 0.