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

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 while minimizing the total connection cost.

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

Idea¶

This problem asks us to connect all points while minimizing the total connection cost.

The cost between two points is their Manhattan distance:

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

We need to satisfy two requirements:

All points must be connected.
The total cost must be as small as possible.

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

We can solve it using Kruskal's Algorithm + Union Find.

Kruskal's Algorithm¶

The core idea of Kruskal's algorithm is:

Build all possible edges

        ↓

Sort all edges by weight
from smallest to largest

        ↓

Consider edges one by one

        ↓

Does this edge connect
two different components?

      /           \
    Yes            No
     ↓              ↓
Take the edge     Skip it
     ↓
Union the two components

        ↓

Stop after selecting n - 1 edges

In this problem, the weight of an edge is the Manhattan distance between two points.

Suppose we have n points.

Every pair of points can be connected, so we consider every pair:

for i in range(n):
    for j in range(i + 1, n):

We start j from:

i + 1

because the distance between i and j is the same as the distance between j and i.

For example:

distance(1, 3) = distance(3, 1)

Therefore, we only need to generate each edge once.

For every pair of points, calculate:

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

and store:

(dist, i, j)

For example:

(4, 0, 1)

means:

point 0 ←── cost 4 ──→ point 1

So every element in edges has the format:

(weight, node1, node2)

After generating all edges, we use:

edges.sort()

Since each edge is stored as:

(dist, i, j)

Python sorts tuples from left to right.

Therefore, it first compares dist.

For example:

Before sorting:

(7, 0, 3)
(4, 0, 1)
(13, 0, 2)
(3, 1, 3)

        ↓

edges.sort()

        ↓

(3, 1, 3)
(4, 0, 1)
(7, 0, 3)
(13, 0, 2)

So the edges are processed from the smallest distance to the largest distance.

Why is this necessary?¶

The goal of Kruskal's algorithm is to build the MST using the cheapest possible edges.

Therefore, we always want to ask:

Can I take the cheapest remaining edge
without creating a cycle?

If yes, take it.

If no, skip it and consider the next cheapest edge.

For example, suppose the available edges are:

A --2-- B
A --5-- C
B --3-- C

We process:

2 → A-B
3 → B-C
5 → A-C

First:

A --2-- B

Take it.

Then:

B --3-- C

Take it.

Now all three nodes are connected:

A --2-- B --3-- C

Total:

2 + 3 = 5

We do not need:

A --5-- C

because A and C are already connected.

Adding it would create a cycle and increase the total cost unnecessarily.

This is why Kruskal processes edges:

smallest weight
      ↓
      ↓
      ↓
largest weight

A useful way to remember Kruskal is:

Always try the cheapest edge first. Keep it only if it connects two previously disconnected components.

Sorting the edges is not enough.

When considering an edge:

u —— v

we need to know whether u and v are already connected.

If they are already connected, adding this edge would create a cycle.

This is exactly what Union Find is good at.

`find`¶

The find function returns the root of a node:

def find(self, node):
    if node != self.parent[node]:
        self.parent[node] = self.find(self.parent[node])
    return self.parent[node]

We also use path compression:

self.parent[node] = self.find(self.parent[node])

so future find operations become faster.

Our union() function is:

def union(self, node1, node2):
    root1 = self.find(node1)
    root2 = self.find(node2)

    if root1 != root2:
        self.parent[root1] = root2
        return True

    return False

The Boolean return value is very useful for Kruskal.

There are two possible situations.

Situation 1: `root1 != root2`¶

Suppose:

Component 1: A -- B

Component 2: C -- D

Now we consider:

B -- C

We get:

find(B) != find(C)

which means B and C belong to different connected components.

Therefore, this edge can safely connect the two components:

A -- B -- C -- D

No cycle is created.

So:

self.parent[root1] = root2
return True

Here True means:

This edge successfully connected two previously disconnected components, so Kruskal should select this edge.

Therefore:

if uf.union(u, v):
    res += dist

Situation 2: `root1 == root2`¶

Suppose we already have:

A -- B -- C

Now we consider another edge:

A ----- C

Since A and C are already connected:

find(A) == find(C)

Adding:

A ----- C

would create:

A ----- C
 \     /
  \   /
    B

which contains a cycle.

Therefore:

return False

Here False means:

These two nodes are already connected. Do not select this edge.

So this code:

if uf.union(u, v):
    res += dist
    edgeCounter += 1

can be understood as:

Try to union u and v

        ↓

union returns True?
      /       \
    Yes        No
     ↓          ↓
Take edge    Skip edge
     ↓
res += dist

This combines cycle detection and union into one function.

When:

union(u, v)

returns False, it means:

u and v are already in the same connected component.

Therefore:

Adding the current edge would create a cycle.

It does not mean that the Union Find tree itself is "a cycle."

Union Find internally always maintains a forest-like parent structure.

The cycle refers to the original graph if we were to add this edge.

This is one of the most important properties of a tree.

A tree with:

n nodes

always has exactly:

n - 1 edges

For example:

1 node  → 0 edges

2 nodes → 1 edge

3 nodes → 2 edges

4 nodes → 3 edges

5 nodes → 4 edges

Why?

Suppose we start with n completely separate nodes:

A    B    C    D

There are initially:

4 connected components

Every valid edge selected by Kruskal merges two different components:

A -- B    C    D

Now there are:

3 components

Add another edge:

A -- B -- C    D

Now:

2 components

Add another:

A -- B -- C -- D

Now:

1 component

We started with:

n components

and every selected edge reduces the number of components by exactly 1.

To go from:

n components

to:

1 component

we need:

n - 1

successful unions.

Therefore, an MST always contains exactly:

n - 1 edges

We use:

edgeCounter = 0

Every time union() returns True, we successfully add one edge to the MST:

if uf.union(u, v):
    res += dist
    edgeCounter += 1

Once:

edgeCounter == n - 1

we know:

All n nodes are connected
+
No cycle exists

Therefore, the MST is complete.

We can immediately:

break

There is no reason to continue checking the remaining edges.

So:

if edgeCounter == n - 1:
    break

is an early stopping condition.

Because we only increment edgeCounter when:

uf.union(u, v)

returns True.

That means every selected edge connects two previously disconnected components.

Therefore, none of the selected edges creates a cycle.

So after selecting n - 1 valid edges, we have:

n nodes
+
n - 1 edges
+
all nodes connected
+
no cycle

which is exactly a tree.

Since we always considered edges from the smallest weight to the largest weight, this tree is a Minimum Spanning Tree.

The entire algorithm can be summarized as:

All points
    ↓
Generate every possible edge
    ↓
Calculate Manhattan distance
    ↓
Store (distance, u, v)
    ↓
Sort edges by distance
    ↓
Smallest edge first
    ↓
For each edge (u, v):
    ↓
union(u, v)
   /      \
 True     False
  ↓         ↓
Take      Skip
edge      edge
  ↓
res += distance
  ↓
edgeCounter += 1
  ↓
edgeCounter == n - 1?
   /       \
 Yes        No
  ↓          ↓
Done       Continue

A useful way to distinguish the two MST algorithms is:

Prim
→ Focuses on nodes
→ Grow one tree
→ Every round adds one new node

Kruskal
→ Focuses on edges
→ Start with many separate components
→ Every successful union merges two components

For this problem:

Prim:
Choose the cheapest node to connect to the current MST.

Kruskal:
Choose the cheapest edge that does not create a cycle.

There are n points.

Since every pair of points can form an edge, the number of edges is:

E = n(n - 1) / 2

which is:

O(n²)

Building all edges:

O(n²)

Sorting all edges:

O(E log E)

Since:

E = O(n²)

the sorting cost is approximately:

O(n² log n)

Union Find operations are very close to constant time with path compression.

Therefore:

Time Complexity: O(n² log n)

Space Complexity: O(n²)

The O(n²) space comes mainly from storing all possible edges.

The three most important ideas in this solution are:

Why sort the edges?

Kruskal is greedy.

Always consider the cheapest remaining edge first.

Why does union() return True or False?

True
→ u and v were in different components
→ this edge does not create a cycle
→ select it

False
→ u and v were already connected
→ this edge would create a cycle
→ skip it

Why stop at n - 1 edges?

A tree with n nodes has exactly n - 1 edges.

Every successful union reduces
the number of components by 1:

n components
    ↓
n - 1
    ↓
n - 2
    ↓
...
    ↓
1 component

Therefore:

n - 1 successful unions
= all nodes connected
= MST complete

The shortest way to remember Kruskal is:

Sort edges from cheapest to most expensive, take an edge if it connects two different components, and stop after selecting n - 1 edges.

Study record

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

Python solution¶

from typing import List

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))

    def find(self, node):
        if node != self.parent[node]:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)

        # Different components:
        # this edge can be safely added to the MST
        if root1 != root2:
            self.parent[root1] = root2
            return True

        # Same component:
        # adding this edge would create a cycle
        return False

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

        # Build all possible edges
        for i in range(n):
            for j in range(i + 1, n):
                x1, y1 = points[i]
                x2, y2 = points[j]

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

                edges.append((dist, i, j))

        # Kruskal: process edges from smallest to largest
        edges.sort()

        uf = UnionFind(n)

        res = 0
        edgeCounter = 0

        for dist, u, v in edges:
            # Only select the edge if it connects
            # two different components
            if uf.union(u, v):
                res += dist
                edgeCounter += 1

                # An MST with n nodes contains exactly n - 1 edges
                if edgeCounter == n - 1:
                    break

        return res

Back to Day 49 Graph VII · All Algorithm notes

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

Idea¶

Kruskal's Algorithm¶

Why is this necessary?¶

find¶

Situation 1: root1 != root2¶

Situation 2: root1 == root2¶

Python solution¶

`find`¶

Situation 1: `root1 != root2`¶

Situation 2: `root1 == root2`¶