codejump
MediumPro challengePythonJavaScriptTypeScript

Graph — Min Cost to Connect All Points

Data StructuresGraphsMinimum Spanning TreeGreedy

solve(points) — points[i] = [x, y]. Connecting two points costs their
Manhattan distance |x1 - x2| + |y1 - y2|. Return the minimum total cost to
connect all points so that every pair is reachable through some path.

That is the minimum spanning tree of the complete graph on the points. Prim's
algorithm in O(n²) is a good fit: the graph is dense, so you do not need a heap.

Examples

solve([[0,0],[2,2],[3,10],[5,2],[7,0]])  → 20
solve([[3,12],[-2,5],[-4,1]])            → 18
solve([[0,0],[1,1]])                     → 2
solve([[0,0]])                           → 0

Sample tests

Test #1Classic example
Input: [[[0,0],[2,2],[3,10],[5,2],[7,0]]]
Output: 20
Test #2Negative coordinates
Input: [[[3,12],[-2,5],[-4,1]]]
Output: 18
Test #3Two points
Input: [[[0,0],[1,1]]]
Output: 2
← All challenges