1584. Min Cost to Connect All Points (Prim)¶

Edited by Charles

Medium · Python · Graph

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

This problem asks us to connect all points with the minimum possible total cost.

Original study notes follow, including intermediate snippets and earlier attempts.

Idea¶

This problem asks us to connect all points with the minimum possible total cost.

The cost of connecting two points is their Manhattan distance:

distance = |x1 - x2| + |y1 - y2|

We need to:

Connect all points.
Avoid unnecessary edges.
Minimize the total edge cost.

This is a classic Minimum Spanning Tree (MST) problem.

We can solve it using Prim's Algorithm.

Prim's Algorithm¶

Prim's algorithm builds one Minimum Spanning Tree by gradually adding nodes.

The basic idea is:

Start with one node
        ↓
Find the cheapest unvisited node
that can connect to the current MST
        ↓
Add it to the MST
        ↓
Update the connection costs
of the remaining nodes
        ↓
Repeat until all nodes are included

Unlike Kruskal's algorithm, Prim focuses on adding nodes rather than sorting and selecting edges.

Key Data Structures¶

We need two arrays:

visit = [False] * n
minDist = [float('inf')] * n

`visit[i]`¶

visit[i] = True

means point i has already been added to the MST.

visit[i] = False

means point i has not been added yet.

`minDist[i]`¶

This is the most important part of the algorithm.

minDist[i]

represents:

The minimum cost required to connect point i to any point already inside the current MST.

For example, suppose the current MST contains:

{0, 2, 4}

Then:

minDist[3]

is:

min(
    distance(0, 3),
    distance(2, 3),
    distance(4, 3)
)

So minDist[i] is not simply the distance from i to the most recently added point.

It is the minimum distance from i to the entire current MST.

Initialization¶

We initialize:

visit = [False] * n
minDist = [float('inf')] * n

Then:

minDist[0] = 0

Why?

Prim's algorithm can start from any node.

We choose point 0 as the starting point.

Since the first point does not need an edge to connect to the MST:

cost = 0

Therefore:

minDist[0] = 0

This guarantees that point 0 will be selected first.

Step 1: Find the Next Node to Add¶

For every round:

u = -1

Here, u represents:

The next node that will be added to the MST.

1 is simply a sentinel value meaning:

No candidate has been selected yet.

Then we search through all nodes:

for i in range(n):
    if not visit[i] and (u == -1 or minDist[i] < minDist[u]):
        u = i

We only consider:

not visit[i]

because nodes already inside the MST should not be selected again.

Among all unvisited nodes, we choose the one with the smallest:

minDist[i]

This means we always choose the cheapest possible way to expand the current MST.

Why Do We Need `u = -1`?¶

At the beginning of each round, we have not selected any candidate yet.

Suppose:

visit   = [True, False, False, False]

minDist = [0,    5,     2,     8]

Initially:

u = -1

When we encounter point 1:

u == -1

so we first set:

u = 1

Then point 2 is considered:

minDist[2] = 2
minDist[1] = 5

Since:

2 < 5

we update:

u = 2

Point 3 has:

minDist[3] = 8

so u remains 2.

Therefore, point 2 is selected.

Step 2: Add `u` to the MST¶

Once we find the cheapest node:

visit[u] = True
res += minDist[u]

visit[u] = True means:

u is now part of the MST.

And:

res += minDist[u]

adds the cost of connecting u to the current MST.

Step 3: Update `minDist`¶

After adding u, this new node may provide a cheaper way to connect some remaining nodes.

Suppose:

u = newly added node
v = an unvisited node

We calculate their Manhattan distance:

dist = abs(x1 - x2) + abs(y1 - y2)

Then:

minDist[v] = min(minDist[v], dist)

This is very important.

We are comparing:

minDist[v]
        ↓
The cheapest connection from v
to the OLD MST

vs.

distance(u, v)
        ↓
The connection from v
to the NEWLY ADDED node u

So:

new minDist[v]

= min(
    old minDist[v],
    distance(u, v)
)

Because u has just joined the MST, distance(u, v) is now another possible way for v to connect to the MST.

Example¶

Consider:

points = [[0,0], [2,2], [3,10], [5,2], [7,0]]

Initially:

MST = {}

visit:
[F, F, F, F, F]

minDist:
[0, ∞, ∞, ∞, ∞]

Round 1¶

The smallest minDist belongs to point 0.

Add point 0:

MST = {0}

res = 0

Now calculate distances from point 0:

Therefore:

minDist:

[0, 4, 13, 7, 7]

Round 2¶

Among unvisited nodes:

point 1 → 4
point 2 → 13
point 3 → 7
point 4 → 7

The minimum is point 1.

Add it:

MST = {0, 1}

res = 0 + 4 = 4

Now use point 1 to update the remaining nodes.

For example:

distance(1, 3)
= |2 - 5| + |2 - 2|
= 3

Previously:

minDist[3] = 7

Now:

minDist[3] = min(7, 3)
           = 3

This demonstrates the meaning of minDist:

Before:

point 3 ← 7 → current MST

After adding point 1:

point 3 ← 3 → point 1

Since point 1 is already in the MST:

minDist[3] becomes 3.

Why Is Prim Greedy?¶

At every step, we choose:

The cheapest possible edge that connects the current MST to a new node.

We never choose a more expensive connection if a cheaper valid connection is available.

Therefore, the MST grows like:

Current MST
     |
     | cheapest connection
     ↓
 New Node

until all nodes are included.

Solution¶

Complexity Analysis¶

Let n be the number of points.

For each of the n rounds:

We scan all n nodes to find the minimum minDist.
We scan all n nodes again to update their distances.

Therefore:

Time Complexity: O(n²)

We use:

visit   → O(n)
minDist → O(n)

Therefore:

Space Complexity: O(n)

An important advantage of this implementation is that we do not explicitly construct all O(n²) edges.

Key Takeaway¶

The most important thing to understand is the meaning of:

minDist[i]

It means:

The minimum cost to connect point i to the current MST.

Therefore, Prim repeatedly performs three steps:

1. Select

   Find the unvisited node u
   with the smallest minDist[u]

                ↓

2. Add

   visit[u] = True
   res += minDist[u]

                ↓

3. Update

   For every unvisited v:

   minDist[v]
       =
   min(
       minDist[v],
       distance(u, v)
   )

A simple way to remember Prim is:

Choose the cheapest node to connect → add it to the MST → use the new node to update the remaining connection costs.

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	August 25, 2026

Python solution¶

from typing import List

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)

        visit = [False] * n
        minDist = [float('inf')] * n
        minDist[0] = 0

        res = 0

        for _ in range(n):
            # No node has been selected in this round
            u = -1

            # Find the unvisited node with the smallest minDist
            for i in range(n):
                if not visit[i] and (u == -1 or minDist[i] < minDist[u]):
                    u = i

            # Add u to the MST
            visit[u] = True
            res += minDist[u]

            # Update minDist for all unvisited nodes
            x, y = points[u]

            for v in range(n):
                if not visit[v]:
                    a, b = points[v]

                    minDist[v] = min(
                        minDist[v],
                        abs(x - a) + abs(y - b)
                    )

        return res

Back to Day 49 Graph VII · All Algorithm notes

1584. Min Cost to Connect All Points (Prim)¶

Idea¶

Prim's Algorithm¶

Key Data Structures¶

visit[i]¶

minDist[i]¶

Initialization¶

Step 1: Find the Next Node to Add¶

Why Do We Need u = -1?¶

Step 2: Add u to the MST¶

Step 3: Update minDist¶

Example¶

Round 1¶

Round 2¶

Why Is Prim Greedy?¶

Solution¶

Complexity Analysis¶

Key Takeaway¶

Python solution¶

`visit[i]`¶

`minDist[i]`¶

Why Do We Need `u = -1`?¶

Step 2: Add `u` to the MST¶

Step 3: Update `minDist`¶