Given points on a plane, the cost of connecting two points is their Manhattan distance, |x₁ − x₂| + |y₁ − y₂|. Return the minimum cost to connect all points, so that there is exactly one simple path between any two.
Before you code
Every pair of points is a possible edge, so the graph is complete. Do you need to build the edge list at all?
Hints
- Keep a key array: the cheapest known connection from each outside point to the tree. Start with key 0 at point 0.
- Repeatedly add the outside point with the smallest key, then lower the keys of the remaining points using their distance to it.
- That is O(n²) time and O(n) memory. Compare it with Kruskal, which must sort about n²/2 edges.
Production & complexity notes
When solving Min cost to connect all points on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Prim's algorithm to reinforce the underlying pattern.
What it practices
The dense-graph version of Prim, from Prim's algorithm.