DSA AnimatorDSA animations
Min Cost to Connect All Points LC #1584 Medium Graph · Prim's MST
Problem

Connect all points with minimum total cost. Cost = Manhattan distance. Prim's MST: pick min-dist non-MST point, add to MST, update minDist.

Example
Input: [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Try Examples
Custom: points as x,y (space separated)
Approach
Prim's MST
minDist[i]=min distance from pt i to MST. Pick min non-MST, add to MST, update minDist. Sum = total cost.
Points & MST Edges
Load an example.
Variables
Pick u
—
minDist[u]
—
cost
—
MST size
—
Step Logic
Press ▶ Play or Next Step.
✓
Ready
0/0
Select example and Play.
Algorithm
1
minDist[0]=0, others=∞
2
Pick min non-MST, add to MST
3
Update minDist for rest
Time
O(n²)
Space
O(n)
Why Prim's

Complete graph (all pairs). minDist[v]=cheapest edge from v to current MST. Greedy pick gives MST.

How to solve Min Cost to Connect All Points

LeetCode 1584 · Medium · Graph · Pattern: Minimum Spanning Tree

Why the obvious approach is slow

Trying every set of n −1 edges is exponential. Connecting everything as cheaply as possible is a minimum spanning tree.

The key idea

Use Prim’s algorithm, which grows one tree from a starting point. Keep, for every point outside the tree, the cheapest edge that connects it to the tree. Each step, add the outside point with the smallest such cost. Then update the costs of the remaining points using the new tree point. After n steps, the sum of the chosen costs is the answer.

Remember

Connect everything cheaply means minimum spanning tree. On a dense graph, array based Prim beats sorting all edges.

Run the animation above on your own input, or watch the 1:50 video explanation of Min Cost to Connect All Points with a dry run and Java code.

More Graph problems