Problem

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Examples

Example 1:

1
2
3
4
5
6

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation: 

We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.

Example 2:

1
2

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18

Solution

Method 1 – Prim’s MST Using minHeap

Intuition

and also we know

In this problem, we already know that given points are the nodes. The distance between each of the nodes, i.e. the manhattan distance is the edges. We want min of these distance, which means this is like Prim’s algorithm. Read here - Minimum Spanning Trees MST - Prim’s Algorithm and also we see

We treat each point as a node and the Manhattan distance between any two points as the edge weight. The goal is to connect all points with the minimum total cost, which is a classic Minimum Spanning Tree (MST) problem. Prim’s algorithm is well-suited here, as it grows the MST by always adding the lowest-cost edge that connects a new node. We have seen implementation of Prim’s Algorithm here - Prims Algorithm Using Adjacency List and Priority Queue. Also, see - Weighted Graph Representation - Adjacency List - Creating Edge Class.

Approach

  1. Start with any point (node) and add it to the MST.
  2. Use a min-heap (priority queue) to always select the edge with the smallest cost that connects a new point to the MST.
  3. For each newly added point, push all edges from it to unvisited points into the heap.
  4. Continue until all points are included in the MST.
  5. The sum of the selected edge weights is the minimum cost to connect all points.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(), ans = 0, cnt = 0;
        vector<bool> vis(n, false);
        vector<int> minDist(n, INT_MAX);
        minDist[0] = 0;
        for (int i = 0; i < n; ++i) {
            int u = -1;
            for (int v = 0; v < n; ++v) {
                if (!vis[v] && (u == -1 || minDist[v] < minDist[u])) u = v;
            }
            vis[u] = true;
            ans += minDist[u];
            for (int v = 0; v < n; ++v) {
                int cost = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]);
                if (!vis[v] && cost < minDist[v]) minDist[v] = cost;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func minCostConnectPoints(points [][]int) int {
    n := len(points)
    vis := make([]bool, n)
    minDist := make([]int, n)
    for i := range minDist { minDist[i] = 1<<31-1 }
    minDist[0] = 0
    ans := 0
    for i := 0; i < n; i++ {
        u := -1
        for v := 0; v < n; v++ {
            if !vis[v] && (u == -1 || minDist[v] < minDist[u]) {
                u = v
            }
        }
        vis[u] = true
        ans += minDist[u]
        for v := 0; v < n; v++ {
            cost := abs(points[u][0]-points[v][0]) + abs(points[u][1]-points[v][1])
            if !vis[v] && cost < minDist[v] {
                minDist[v] = cost
            }
        }
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length, ans = 0;
        boolean[] vis = new boolean[n];
        int[] minDist = new int[n];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[0] = 0;
        for (int i = 0; i < n; i++) {
            int u = -1;
            for (int v = 0; v < n; v++) {
                if (!vis[v] && (u == -1 || minDist[v] < minDist[u])) u = v;
            }
            vis[u] = true;
            ans += minDist[u];
            for (int v = 0; v < n; v++) {
                int cost = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
                if (!vis[v] && cost < minDist[v]) minDist[v] = cost;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun minCostConnectPoints(points: Array<IntArray>): Int {
        val n = points.size
        val vis = BooleanArray(n)
        val minDist = IntArray(n) { Int.MAX_VALUE }
        minDist[0] = 0
        var ans = 0
        repeat(n) {
            var u = -1
            for (v in 0 until n) {
                if (!vis[v] && (u == -1 || minDist[v] < minDist[u])) u = v
            }
            vis[u] = true
            ans += minDist[u]
            for (v in 0 until n) {
                val cost = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1])
                if (!vis[v] && cost < minDist[v]) minDist[v] = cost
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def minCostConnectPoints(self, points: list[list[int]]) -> int:
        n = len(points)
        vis = [False] * n
        min_dist = [float('inf')] * n
        min_dist[0] = 0
        ans = 0
        for _ in range(n):
            u = -1
            for v in range(n):
                if not vis[v] and (u == -1 or min_dist[v] < min_dist[u]):
                    u = v
            vis[u] = True
            ans += min_dist[u]
            for v in range(n):
                cost = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
                if not vis[v] and cost < min_dist[v]:
                    min_dist[v] = cost
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

impl Solution {
    pub fn min_cost_connect_points(points: Vec<Vec<i32>>) -> i32 {
        let n = points.len();
        let mut vis = vec![false; n];
        let mut min_dist = vec![i32::MAX; n];
        min_dist[0] = 0;
        let mut ans = 0;
        for _ in 0..n {
            let mut u = None;
            for v in 0..n {
                if !vis[v] && (u.is_none() || min_dist[v] < min_dist[u.unwrap()]) {
                    u = Some(v);
                }
            }
            let u = u.unwrap();
            vis[u] = true;
            ans += min_dist[u];
            for v in 0..n {
                let cost = (points[u][0] - points[v][0]).abs() + (points[u][1] - points[v][1]).abs();
                if !vis[v] && cost < min_dist[v] {
                    min_dist[v] = cost;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    minCostConnectPoints(points: number[][]): number {
        const n = points.length;
        const vis = Array(n).fill(false);
        const minDist = Array(n).fill(Number.MAX_SAFE_INTEGER);
        minDist[0] = 0;
        let ans = 0;
        for (let i = 0; i < n; i++) {
            let u = -1;
            for (let v = 0; v < n; v++) {
                if (!vis[v] && (u === -1 || minDist[v] < minDist[u])) u = v;
            }
            vis[u] = true;
            ans += minDist[u];
            for (let v = 0; v < n; v++) {
                const cost = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
                if (!vis[v] && cost < minDist[v]) minDist[v] = cost;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) — For each of the n nodes, we scan all other nodes to find the minimum edge.
  • 🧺 Space complexity: O(n) — For the visited and minDist arrays.

Method 2 – Kruskal’s MST Using Union-Find

Intuition

We can also solve the minimum cost to connect all points by building all possible edges (with their Manhattan distances) and sorting them by cost. Then, using Kruskal’s algorithm, we add the smallest edges one by one, connecting components using Union-Find, until all points are connected. This approach is efficient when the number of points is not too large.

Approach

  1. Generate all possible edges between points, with their Manhattan distances as weights.
  2. Sort all edges by weight (cost).
  3. Initialize a Union-Find (Disjoint Set Union) structure to keep track of connected components.
  4. Iterate through the sorted edges:
    • For each edge, if the two points are not already connected, add the edge to the MST and union their components.
    • Stop when all points are connected (n-1 edges added).
  5. The sum of the selected edge weights is the minimum cost to connect all points.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length, ans = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                pq.add(new int[]{findDist(points, i, j), i, j});
            }
        }
        int count = 0;
        UnionFind uf = new UnionFind(n);
        while (count < n - 1) {
            int[] edge = pq.poll();
            if (uf.find(edge[1]) != uf.find(edge[2])) {
                ans += edge[0];
                count++;
                uf.union(edge[1], edge[2]);
            }
        }
        return ans;
    }
    private int findDist(int[][] points, int a, int b) {
        return Math.abs(points[a][0] - points[b][0]) + Math.abs(points[a][1] - points[b][1]);
    }
    class UnionFind {
        int[] parent;
        UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        void union(int a, int b) {
            parent[find(a)] = parent[find(b)];
        }
        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class UnionFind {
public:
    vector<int> parent;
    UnionFind(int n) : parent(n) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    void unite(int x, int y) {
        parent[find(x)] = find(y);
    }
};
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(), ans = 0, count = 0;
        vector<tuple<int, int, int>> edges;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                edges.emplace_back(abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), i, j);
        sort(edges.begin(), edges.end());
        UnionFind uf(n);
        for (auto& [cost, u, v] : edges) {
            if (uf.find(u) != uf.find(v)) {
                ans += cost;
                uf.unite(u, v);
                if (++count == n - 1) break;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

type edge struct{cost, u, v int}
type UnionFind struct{parent []int}
func (uf *UnionFind) find(x int) int {
    if uf.parent[x] != x { uf.parent[x] = uf.find(uf.parent[x]) }
    return uf.parent[x]
}
func (uf *UnionFind) union(x, y int) { uf.parent[uf.find(x)] = uf.find(y) }
func minCostConnectPoints(points [][]int) int {
    n := len(points)
    edges := []edge{}
    for i := 0; i < n; i++ {
        for j := i+1; j < n; j++ {
            cost := abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1])
            edges = append(edges, edge{cost, i, j})
        }
    }
    sort.Slice(edges, func(i, j int) bool { return edges[i].cost < edges[j].cost })
    uf := UnionFind{make([]int, n)}
    for i := range uf.parent { uf.parent[i] = i }
    ans, count := 0, 0
    for _, e := range edges {
        if uf.find(e.u) != uf.find(e.v) {
            ans += e.cost
            uf.union(e.u, e.v)
            count++
            if count == n-1 { break }
        }
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    fun minCostConnectPoints(points: Array<IntArray>): Int {
        val n = points.size
        val edges = mutableListOf<Triple<Int, Int, Int>>()
        for (i in 0 until n) for (j in i+1 until n)
            edges.add(Triple(
                Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]), i, j))
        edges.sortBy { it.first }
        val uf = UnionFind(n)
        var ans = 0
        var count = 0
        for ((cost, u, v) in edges) {
            if (uf.find(u) != uf.find(v)) {
                ans += cost
                uf.union(u, v)
                count++
                if (count == n-1) break
            }
        }
        return ans
    }
    class UnionFind(n: Int) {
        private val parent = IntArray(n) { it }
        fun find(x: Int): Int {
            if (parent[x] != x) parent[x] = find(parent[x])
            return parent[x]
        }
        fun union(x: Int, y: Int) { parent[find(x)] = find(y) }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        self.parent[self.find(x)] = self.find(y)
class Solution:
    def minCostConnectPoints(self, points: list[list[int]]) -> int:
        n = len(points)
        edges = []
        for i in range(n):
            for j in range(i+1, n):
                cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                edges.append((cost, i, j))
        edges.sort()
        uf = UnionFind(n)
        ans = count = 0
        for cost, u, v in edges:
            if uf.find(u) != uf.find(v):
                ans += cost
                uf.union(u, v)
                count += 1
                if count == n-1:
                    break
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

struct UnionFind {
    parent: Vec<usize>,
}
impl UnionFind {
    fn new(n: usize) -> Self {
        Self { parent: (0..n).collect() }
    }
    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }
    fn union(&mut self, x: usize, y: usize) {
        let px = self.find(x);
        let py = self.find(y);
        self.parent[px] = py;
    }
}
impl Solution {
    pub fn min_cost_connect_points(points: Vec<Vec<i32>>) -> i32 {
        let n = points.len();
        let mut edges = vec![];
        for i in 0..n {
            for j in i+1..n {
                let cost = (points[i][0] - points[j][0]).abs() + (points[i][1] - points[j][1]).abs();
                edges.push((cost, i, j));
            }
        }
        edges.sort_unstable();
        let mut uf = UnionFind::new(n);
        let mut ans = 0;
        let mut count = 0;
        for (cost, u, v) in edges {
            if uf.find(u) != uf.find(v) {
                ans += cost;
                uf.union(u, v);
                count += 1;
                if count == n - 1 { break; }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class UnionFind {
    parent: number[];
    constructor(n: number) {
        this.parent = Array.from({length: n}, (_, i) => i);
    }
    find(x: number): number {
        if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x: number, y: number) {
        this.parent[this.find(x)] = this.find(y);
    }
}
class Solution {
    minCostConnectPoints(points: number[][]): number {
        const n = points.length;
        const edges: [number, number, number][] = [];
        for (let i = 0; i < n; i++)
            for (let j = i + 1; j < n; j++)
                edges.push([
                    Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]),
                    i, j
                ]);
        edges.sort((a, b) => a[0] - b[0]);
        const uf = new UnionFind(n);
        let ans = 0, count = 0;
        for (const [cost, u, v] of edges) {
            if (uf.find(u) !== uf.find(v)) {
                ans += cost;
                uf.union(u, v);
                count++;
                if (count === n - 1) break;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2 \, \log n) — Building all edges takes O(n^2), sorting takes O(n^2 \log n), and union-find operations are nearly constant time.
  • 🧺 Space complexity: O(n^2) — For storing all possible edges.