Graph Theory37 sections · 1633 units
Open in Course

Problem - Min Cost to Connect All Points

LeetCode 1584 - Complete gr...

You are given a list of 2D2D points. Connect all points with the minimum total cost. The cost of connecting two points is the Manhattan distance between them. This is an MST problem on a complete graph.

Every pair of points has an edge. The job: find the MST. The twist: edges are implicit, not given directly. You compute them on demand. This tests whether you can apply MST to geometric problems. With nn points, there are O(n2)O(n^2) edges, so you need an efficient MST algorithm.