Min Cost to Connect Points
Min Cost to Connect Points Problem
You are given a 2D integer array, points, where each points[i] = [xi, yi] represents a unique point on a 2D plane.
The cost of connecting two points, [xi, yi] and [xj, yj], is defined by their Manhattan distance: |xi – xj| + |yi – yj|.
Your task is to return the minimum cost required to connect all points so that there is exactly one path between every pair of points.
Examples related to Min Cost to Connect Points
Example:
Illustration:
Input: points = [[0,0],[2,2],[3,3],[2,4],[4,2]]
Output: 10
Output: 10
Constraints:
- 1 <= points.length <= 1000
- -1000 <= xi, yi <= 1000
Hints to solve Min Cost to Connect Points
Recommended Time & Space Complexity
Aim for a solution with a time complexity of O((n²) log n) and a space complexity of O(n²), where n is the number of points.
Hint 1:
- This problem can be visualized as a graph, where points are nodes. The goal is to connect all nodes into a single component with the least cost.
- Can you think of a graph algorithm that builds such a structure efficiently?
Hint 2:
-
First, calculate the edges by iterating through all pairs of points and computing the Manhattan distance between them. Then, sort the edges in ascending order of weights.
-
Finally, process these edges, connecting nodes using Union-Find and adding the edge’s weight to the total cost when it successfully forms part of the MST. The result will be the minimum cost.
Hint 3:
First, calculate the edges by iterating through all pairs of points and computing the Manhattan distance between them. Then, sort the edges in ascending order of weights.
Finally, process these edges, connecting nodes using Union-Find and adding the edge’s weight to the total cost when it successfully forms part of the MST. The result will be the minimum cost.
Methods to Solve Min Cost to Connect Points
There are mainly 3 approach to solve Min Cost to Connect Points problem:
- Kruskal’s Algorithm Method
- Prim’s Algorithm Method
- Prim’s Algorithm (Optimal)
1. Kruskal’s Algorithm Method
In this method, treat each point as a node and compute all possible edges with weights as the Manhattan distance.
Sort the edges, and use Union-Find to build a Minimum Spanning Tree (MST) by adding the smallest edges until all points are connected.
- Time complexity: O((n²) log n)
- Space complexity: O(n²)
Code:
C++
Java
Python
JavaScript
C++
class DSU {
public:
vector Parent, Size;
DSU(int n) : Parent(n + 1), Size(n + 1, 1) {
for (int i = 0; i <= n; ++i) Parent[i] = i;
}
int find(int node) {
if (Parent[node] != node) {
Parent[node] = find(Parent[node]);
}
return Parent[node];
}
bool unionSets(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv) return false;
if (Size[pu] < Size[pv]) swap(pu, pv);
Size[pu] += Size[pv];
Parent[pv] = pu;
return true;
}
};
class Solution {
public:
int minCostConnectPoints(vector>& points) {
int n = points.size();
DSU dsu(n);
vector> edges;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int dist = abs(points[i][0] - points[j][0]) +
abs(points[i][1] - points[j][1]);
edges.push_back({dist, i, j});
}
}
sort(edges.begin(), edges.end());
int res = 0;
for (auto& [dist, u, v] : edges) {
if (dsu.unionSets(u, v)) {
res += dist;
}
}
return res;
}
};
Java
public class DSU {
int[] Parent, Size;
public DSU(int n) {
Parent = new int[n + 1];
Size = new int[n + 1];
for (int i = 0; i <= n; i++) Parent[i] = i;
Arrays.fill(Size, 1);
}
public int find(int node) {
if (Parent[node] != node) {
Parent[node] = find(Parent[node]);
}
return Parent[node];
}
public boolean union(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv) return false;
if (Size[pu] < Size[pv]) {
int temp = pu;
pu = pv;
pv = temp;
}
Size[pu] += Size[pv];
Parent[pv] = pu;
return true;
}
}
public class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
DSU dsu = new DSU(n);
List edges = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int dist = Math.abs(points[i][0] - points[j][0]) +
Math.abs(points[i][1] - points[j][1]);
edges.add(new int[] {dist, i, j});
}
}
edges.sort((a, b) -> Integer.compare(a[0], b[0]));
int res = 0;
for (int[] edge : edges) {
if (dsu.union(edge[1], edge[2])) {
res += edge[0];
}
}
return res;
}
}
Python
class DSU:
def __init__(self, n):
self.Parent = list(range(n + 1))
self.Size = [1] * (n + 1)
def find(self, node):
if self.Parent[node] != node:
self.Parent[node] = self.find(self.Parent[node])
return self.Parent[node]
def union(self, u, v):
pu = self.find(u)
pv = self.find(v)
if pu == pv:
return False
if self.Size[pu] < self.Size[pv]:
pu, pv = pv, pu
self.Size[pu] += self.Size[pv]
self.Parent[pv] = pu
return True
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
dsu = DSU(n)
edges = []
for i in range(n):
x1, y1 = points[i]
for j in range(i + 1, n):
x2, y2 = points[j]
dist = abs(x1 - x2) + abs(y1 - y2)
edges.append((dist, i, j))
edges.sort()
res = 0
for dist, u, v in edges:
if dsu.union(u, v):
res += dist
return res
JavaScript
class DSU {
constructor(n) {
this.Parent = Array.from({ length: n + 1 }, (_, i) => i);
this.Size = Array(n + 1).fill(1);
}
/**
* @param {number} node
* @return {number}
*/
find(node) {
if (this.Parent[node] !== node) {
this.Parent[node] = this.find(this.Parent[node]);
}
return this.Parent[node];
}
/**
* @param {number} u
* @param {number} v
* @return {boolean}
*/
union(u, v) {
let pu = this.find(u), pv = this.find(v);
if (pu === pv) return false;
if (this.Size[pu] < this.Size[pv]) [pu, pv] = [pv, pu];
this.Size[pu] += this.Size[pv];
this.Parent[pv] = pu;
return true;
}
}
class Solution {
/**
* @param {number[][]} points
* @return {number}
*/
minCostConnectPoints(points) {
const n = points.length;
const dsu = new DSU(n);
const edges = [];
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const dist = Math.abs(points[i][0] - points[j][0]) +
Math.abs(points[i][1] - points[j][1]);
edges.push([dist, i, j]);
}
}
edges.sort((a, b) => a[0] - b[0]);
let res = 0;
for (const [dist, u, v] of edges) {
if (dsu.union(u, v)) {
res += dist;
}
}
return res;
}
}
2. Prim’s Algorithm Method
Start with any point as part of the MST. Use a priority queue to pick the smallest edge connecting the tree to a new point.
Continue until all points are included in the MST.
- Time complexity: O((n²) log n)
- Space complexity: O(n²)
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
int minCostConnectPoints(vector>& points) {
int N = points.size();
unordered_map>> adj;
for (int i = 0; i < N; i++) {
int x1 = points[i][0];
int y1 = points[i][1];
for (int j = i + 1; j < N; j++) {
int x2 = points[j][0];
int y2 = points[j][1];
int dist = abs(x1 - x2) + abs(y1 - y2);
adj[i].push_back({dist, j});
adj[j].push_back({dist, i});
}
}
int res = 0;
unordered_set visit;
priority_queue, vector>,
greater>> minH;
minH.push({0, 0});
while (visit.size() < N) {
auto curr = minH.top();
minH.pop();
int cost = curr.first;
int i = curr.second;
if (visit.count(i)) {
continue;
}
res += cost;
visit.insert(i);
for (const auto& nei : adj[i]) {
int neiCost = nei.first;
int neiIndex = nei.second;
if (!visit.count(neiIndex)) {
minH.push({neiCost, neiIndex});
}
}
}
return res;
}
};
Java
public class Solution {
public int minCostConnectPoints(int[][] points) {
int N = points.length;
Map> adj = new HashMap<>();
for (int i = 0; i < N; i++) {
int x1 = points[i][0];
int y1 = points[i][1];
for (int j = i + 1; j < N; j++) {
int x2 = points[j][0];
int y2 = points[j][1];
int dist = Math.abs(x1 - x2) + Math.abs(y1 - y2);
adj.computeIfAbsent(i, k -> new ArrayList<>()).add(new int[]{dist, j});
adj.computeIfAbsent(j, k -> new ArrayList<>()).add(new int[]{dist, i});
}
}
int res = 0;
Set visit = new HashSet<>();
PriorityQueue minH = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
minH.offer(new int[]{0, 0});
while (visit.size() < N) {
int[] curr = minH.poll();
int cost = curr[0];
int i = curr[1];
if (visit.contains(i)) {
continue;
}
res += cost;
visit.add(i);
for (int[] nei : adj.getOrDefault(i, Collections.emptyList())) {
int neiCost = nei[0];
int neiIndex = nei[1];
if (!visit.contains(neiIndex)) {
minH.offer(new int[]{neiCost, neiIndex});
}
}
}
return res;
}
}
Python
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
N = len(points)
adj = {i: [] for i in range(N)}
for i in range(N):
x1, y1 = points[i]
for j in range(i + 1, N):
x2, y2 = points[j]
dist = abs(x1 - x2) + abs(y1 - y2)
adj[i].append([dist, j])
adj[j].append([dist, i])
res = 0
visit = set()
minH = [[0, 0]]
while len(visit) < N:
cost, i = heapq.heappop(minH)
if i in visit:
continue
res += cost
visit.add(i)
for neiCost, nei in adj[i]:
if nei not in visit:
heapq.heappush(minH, [neiCost, nei])
return res
JavaScript
class Solution {
/**
* @param {number[][]} points
* @return {number}
*/
minCostConnectPoints(points) {
const N = points.length;
const adj = new Map();
for (let i = 0; i < N; i++) {
adj.set(i, []);
}
for (let i = 0; i < N; i++) {
const [x1, y1] = points[i];
for (let j = i + 1; j < N; j++) {
const [x2, y2] = points[j];
const dist = Math.abs(x1 - x2) + Math.abs(y1 - y2);
adj.get(i).push([dist, j]);
adj.get(j).push([dist, i]);
}
}
let res = 0;
const visit = new Set();
const minHeap = new MinPriorityQueue(entry => entry[0]);
minHeap.push([0, 0]);
while (visit.size < N) {
const [cost, i] = minHeap.pop();
if (visit.has(i)) continue;
res += cost;
visit.add(i);
for (const [neiCost, nei] of adj.get(i)) {
if (!visit.has(nei)) {
minHeap.push([neiCost, nei]);
}
}
}
return res;
}
}
3. Prim’s Algorithm (Optimal) Method
This version improves efficiency by using a min-heap and an adjacency list to track the smallest edge for each point. It reduces redundant edge calculations, making the process faster for larger datasets.
- Time complexity: O(n²)
- Space complexity: O(n)
Code:
C++
Java
Python
JavaScript
C++
class Solution {
public:
int minCostConnectPoints(vector>& points) {
int n = points.size(), node = 0;
vector dist(n, 100000000);
vector visit(n, false);
int edges = 0, res = 0;
while (edges < n - 1) {
visit[node] = true;
int nextNode = -1;
for (int i = 0; i < n; i++) {
if (visit[i]) continue;
int curDist = abs(points[i][0] - points[node][0]) +
abs(points[i][1] - points[node][1]);
dist[i] = min(dist[i], curDist);
if (nextNode == -1 || dist[i] < dist[nextNode]) {
nextNode = i;
}
}
res += dist[nextNode];
node = nextNode;
edges++;
}
return res;
}
};
Java
public class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length, node = 0;
int[] dist = new int[n];
boolean[] visit = new boolean[n];
Arrays.fill(dist, 100000000);
int edges = 0, res = 0;
while (edges < n - 1) {
visit[node] = true;
int nextNode = -1;
for (int i = 0; i < n; i++) {
if (visit[i]) continue;
int curDist = Math.abs(points[i][0] - points[node][0]) +
Math.abs(points[i][1] - points[node][1]);
dist[i] = Math.min(dist[i], curDist);
if (nextNode == -1 || dist[i] < dist[nextNode]) {
nextNode = i;
}
}
res += dist[nextNode];
node = nextNode;
edges++;
}
return res;
}
}
Python
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n, node = len(points), 0
dist = [100000000] * n
visit = [False] * n
edges, res = 0, 0
while edges < n - 1:
visit[node] = True
nextNode = -1
for i in range(n):
if visit[i]:
continue
curDist = (abs(points[i][0] - points[node][0]) +
abs(points[i][1] - points[node][1]))
dist[i] = min(dist[i], curDist)
if nextNode == -1 or dist[i] < dist[nextNode]:
nextNode = i
res += dist[nextNode]
node = nextNode
edges += 1
return res
JavaScript
class Solution {
/**
* @param {number[][]} points
* @return {number}
*/
minCostConnectPoints(points) {
const n = points.length;
let node = 0;
const dist = new Array(n).fill(100000000);
const visit = new Array(n).fill(false);
let edges = 0, res = 0;
while (edges < n - 1) {
visit[node] = true;
let nextNode = -1;
for (let i = 0; i < n; i++) {
if (visit[i]) continue;
const curDist = Math.abs(points[i][0] - points[node][0]) +
Math.abs(points[i][1] - points[node][1]);
dist[i] = Math.min(dist[i], curDist);
if (nextNode === -1 || dist[i] < dist[nextNode]) {
nextNode = i;
}
}
res += dist[nextNode];
node = nextNode;
edges++;
}
return res;
}
}
