leetExpert
Practice

Min Cost to Connect All Points

Module 23 · Graphs

Problem

Given n points on a 2D plane, the cost to connect two points [xi, yi] and [xj, yj] is their Manhattan distance: |xi - xj| + |yi - yj|. Return the minimum total cost to connect all points such that there is exactly one path between any two points (i.e. build a Minimum Spanning Tree over the complete graph these points define). (LeetCode 1584.)

Examples

Example 1

Inputpoints = [[0,0],[2,2],[3,10],[5,2],[7,0]]Output20

Constraints

1 ≤ points.length ≤ 1000, coordinates in ±10⁴.

Attempt it first

Every pair of points can be connected directly (there's no notion of "no edge exists" here — any two points have a well-defined Manhattan distance), so this is a complete graph: n points imply n(n-1)/2 possible edges. Before opening anything, revisit the Minimum Spanning Trees concept lesson's comparison of Kruskal's vs. Prim's, and think specifically about what a COMPLETE graph does to that comparison — what happens to Kruskal's edge list, and to the cost of even constructing it, when E is O(n²) instead of some smaller number tied to a sparser structure?