Min Cost to Connect All Points solution and explanation
Google
9 more videos on this problem
Prim's Algorithm - Minimum Spanning Tree - Min Cost to Connect all Points - Leetcode 1584 - PythonNeetCode · 22:08 · 147K views
Min Cost to Connect All Points | Prim's Algorithm | META | Graph Concepts & Qns - 35 | Leetcode-1584codestorywithMIK · 19:04 · 22K views
Min Cost to Connect All Points | Kruskal's Algorithm | Graph Concepts & Qns - 37 | Leetcode-1584codestorywithMIK · 11:32 · 9K views
Min Cost to Connect All Points (Prim's Algorithm to Create MST) - Leetcode 1584 - Graphs (Python)Greg Hogg · 14:45 · 9K views
Min Cost to Connect All Points | Leetcode 1584 | Minimum Spanning tree Nailed | Live coding sessionCoding Decoded · 13:52 · 5K views
Min Cost to Connect All Points | Graph ProblemShradha Khapra · 21:16 · 5K views
Leetcode 1584. Min Cost Connect Points | HindiThinkCode · 7:21 · 2K views
LeetCode 1584. Min Cost to Connect All Points | Kruskal's Algorithm | PythonAH Tech · 6:04 · 2K views
【每日一题】1584. Min Cost to Connect All Points, 9/13/2020Huifeng Guan · 35:46 · 1K views
1584. Min Cost to Connect All Points (Leetcode Medium)Programming Live with Larry · 6:33 · 1K views
The 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.
Example 1:
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:
Input: points = [[3,12],[-2,5],[-4,1]] Output: 18
Constraints:
1 <= points.length <= 1000-106 <= xi, yi <= 106- All pairs
(xi, yi)are distinct.
Approach overview
Problem Overview: You are given n points on a 2D plane. The cost to connect two points equals their Manhattan distance |x1-x2| + |y1-y2|. The goal is to connect every point so that all points are reachable from each other while minimizing the total connection cost. This is a classic Minimum Spanning Tree (MST) problem on a complete graph where each pair of points forms an edge weighted by Manhattan distance.
Approach 1: Kruskal's Algorithm with Union-Find (Time: O(n^2 log n), Space: O(n^2))
Model the problem as a graph with n vertices. Since every pair of points can connect, generate all n(n-1)/2 edges and compute their Manhattan distances. Sort these edges by cost. Then iterate through the sorted list and use a Union-Find (Disjoint Set Union) structure to check whether two points already belong to the same component. If they do not, union them and add the edge cost to the total. Continue until n-1 edges are selected. This greedy strategy guarantees a valid MST because edges are processed from smallest weight to largest. This approach works well when you are comfortable managing edge lists and union operations using Union Find.
Approach 2: Prim's Algorithm (Time: O(n^2), Space: O(n))
Prim's algorithm builds the MST incrementally. Start from any point and mark it as visited. For every unvisited point, maintain the minimum cost required to connect it to the current MST. At each step, pick the unvisited point with the smallest connection cost, add it to the MST, and update distances for the remaining points. Because the graph is dense (every pair of points has an edge), computing distances on the fly avoids storing all edges. This leads to O(n^2) time and O(n) extra space. The approach relies heavily on greedy expansion and is often easier to implement for dense graph problems involving minimum spanning tree construction.
Recommended for interviews: Prim's algorithm is usually the expected solution. The graph is fully connected, so generating all edges for Kruskal introduces unnecessary overhead. Demonstrating Kruskal first shows you recognize the MST pattern, but implementing Prim with a distance array shows deeper understanding of how MST algorithms behave on dense graphs.
Approach 1: Approach 1: Kruskal's Algorithm with Union-Find
This approach involves treating the points as nodes of a graph and the Manhattan distance between them as the edge weights. The problem translates to finding a Minimum Spanning Tree (MST), which connects all nodes with the minimum edge weight.
Kruskal's algorithm is a popular choice for this kind of problem. It works as follows:
- Calculate the Manhattan distance between all pairs of points to create the edges of the graph.
- Sort all edges by their weight (distance).
- Initialize a Union-Find (Disjoint Set Union) structure to track connected components.
- Iterate through the sorted edge list, adding an edge to the MST if it connects two previously unconnected components.
This approach efficiently computes the minimum cost of connecting all points.
class Solution:
def minCostConnectPoints(self, points):
def find(parent, i):
if parent[i] != i:
parent[i] = find(parent, parent[i])
return parent[i]
def union(parent, rank, x, y):
rootX = find(parent, x)
rootY = find(parent, y)
if rootX != rootY:
if rank[rootX] < rank[rootY]:
parent[rootX] = rootY
elif rank[rootX] > rank[rootY]:
parent[rootY] = rootX
else:
parent[rootY] = rootX
rank[rootX] += 1
def manhattan(p1, p2):
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
n = len(points)
edges = [(manhattan(points[i], points[j]), i, j) for i in range(n) for j in range(i + 1, n)]
edges.sort()
parent = list(range(n))
rank = [0] * n
min_cost = 0
edges_used = 0
for weight, u, v in edges:
if find(parent, u) != find(parent, v):
union(parent, rank, u, v)
min_cost += weight
edges_used += 1
if edges_used == n - 1:
break
return min_costimport java.util.*;
class Solution {
static class Edge implements Comparable<Edge> {
int point1, point2, weight;
Edge(int point1, int point2, int weight) {
this.point1 = point1;
this.point2 = point2;
this.weight = weight;
}
public int compareTo(Edge other) {
return Integer.compare(this.weight, other.weight);
}
}
int find(int[] parent, int i) {
if (parent[i] != i) {
parent[i] = find(parent, parent[i]);
}
return parent[i];
}
void union(int[] parent, int[] rank, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
public int minCostConnectPoints(int[][] points) {
List<Edge> edges = new ArrayList<>();
int n = points.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int weight = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
edges.add(new Edge(i, j, weight));
}
}
Collections.sort(edges);
int[] parent = new int[n];
int[] rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
int minCost = 0;
int edgesUsed = 0;
for (Edge edge : edges) {
if (find(parent, edge.point1) != find(parent, edge.point2)) {
union(parent, rank, edge.point1, edge.point2);
minCost += edge.weight;
edgesUsed++;
if (edgesUsed == n - 1) {
break;
}
}
}
return minCost;
}
}#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
class Solution {
struct Edge {
int point1;
int point2;
int weight;
};
int find(vector<int>& parent, int i) {
if (parent[i] != i) {
parent[i] = find(parent, parent[i]);
}
return parent[i];
}
void unionSets(vector<int>& parent, vector<int>& rank, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size();
vector<Edge> edges;
for (int i = 0; i < n - 1; ++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({ i, j, dist });
}
}
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.weight < b.weight; });
vector<int> parent(n);
vector<int> rank(n, 0);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
int minCost = 0;
int edgesUsed = 0;
for (const auto& edge : edges) {
if (find(parent, edge.point1) != find(parent, edge.point2)) {
unionSets(parent, rank, edge.point1, edge.point2);
minCost += edge.weight;
edgesUsed++;
if (edgesUsed == n - 1) {
break;
}
}
}
return minCost;
}
};var minCostConnectPoints = function(points) {
const n = points.length;
const edges = [];
for (let i = 0; i < n - 1; 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([i, j, dist]);
}
}
edges.sort((a, b) => a[2] - b[2]);
const parent = Array(n).fill().map((_, index) => index);
const rank = Array(n).fill(0);
const find = (i) => {
if (parent[i] !== i) {
parent[i] = find(parent[i]);
}
return parent[i];
};
const union = (x, y) => {
const rootX = find(x);
const rootY = find(y);
if (rootX !== rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
};
let minCost = 0;
let edgesUsed = 0;
for (const [u, v, weight] of edges) {
if (find(u) !== find(v)) {
union(u, v);
minCost += weight;
edgesUsed++;
if (edgesUsed === n - 1) break;
}
}
return minCost;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int find(int parent[], int i) {
if (parent[i] != i) {
parent[i] = find(parent, parent[i]);
}
return parent[i];
}
void unionSets(int parent[], int rank[], int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
int minCostConnectPoints(int** points, int pointsSize, int* pointsColSize) {
int numEdges = pointsSize * (pointsSize - 1) / 2;
int edges[numEdges][3]; // each edge represented as [distance, point1, point2]
int k = 0;
for (int i = 0; i < pointsSize - 1; i++) {
for (int j = i + 1; j < pointsSize; j++) {
int dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
edges[k][0] = dist;
edges[k][1] = i;
edges[k][2] = j;
k++;
}
}
// Sort edges by distance
qsort(edges, numEdges, sizeof(edges[0]), [](const void *a, const void *b) -> int {
return ((int*)a)[0] - ((int*)b)[0];
});
// Kruskal's algorithm
int parent[pointsSize];
int rank[pointsSize];
for (int i = 0; i < pointsSize; i++) {
parent[i] = i;
rank[i] = 0;
}
int minCost = 0;
int edgesUsed = 0;
for (int i = 0; i < numEdges && edgesUsed < pointsSize - 1; i++) {
int dist = edges[i][0], point1 = edges[i][1], point2 = edges[i][2];
if (find(parent, point1) != find(parent, point2)) {
unionSets(parent, rank, point1, point2);
minCost += dist;
edgesUsed++;
}
}
return minCost;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinCostConnectPoints(int[][] points) {
int n = points.Length;
List<int[]> edges = new List<int[]>();
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int weight = Math.Abs(points[i][0] - points[j][0]) + Math.Abs(points[i][1] - points[j][1]);
edges.Add(new int[] { i, j, weight });
}
}
edges.Sort((a, b) => a[2] - b[2]);
int[] parent = new int[n];
int[] rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int find(int i) {
if (parent[i] != i) {
parent[i] = find(parent[i]);
}
return parent[i];
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
int minCost = 0;
int edgesUsed = 0;
foreach (var edge in edges) {
int u = edge[0], v = edge[1], weight = edge[2];
if (find(u) != find(v)) {
union(u, v);
minCost += weight;
edgesUsed++;
if (edgesUsed == n - 1) break;
}
}
return minCost;
}
}The Python version defines helper functions for union-find operations and the Manhattan distance calculation. It uses a list comprehension to create a sorted list of edges by calculating Manhattan distances between all pairs of points. Using a simple union-find structure, it efficiently builds the Minimum Spanning Tree by only connecting points belonging to different components, ensuring cycles do not occur. The function returns the constructed MST's total minimum cost.
Just like in other languages, the time complexity is O(E log E) due to sorting the edges, with efficient union-find operations. Space complexity is O(n) due to storage for the parent and rank arrays and edge list, where n is the number of points.
Approach 2: Approach 2: Prim's Algorithm
Another approach uses Prim's algorithm to construct the Minimum Spanning Tree (MST). Rather than sorting edges, Prim's method grows the MST one vertex at a time, starting from an arbitrary vertex and adding the minimum cost edge that expands the MST.
The steps involved are:
- Initialize an array to track minimum costs from each node.
- Use a priority queue to select the next edge with the smallest cost.
- Iterate over nodes, updating the priority queue with potential edges to unvisited nodes.
This approach offers a clear alternative to Kruskal's, particularly well-suited to densely connected systems.
import heapq
class Solution:
def minCostConnectPoints(self, points):
n = len(points)
minDist = [float('inf')] * n
minDist[0] = 0
visited = [False] * n
heap = [(0, 0)] # (distance, point)
totalCost = 0
while heap:
cost, point = heapq.heappop(heap)
if visited[point]:
continue
visited[point] = True
totalCost += cost
for next_point in range(n):
if not visited[next_point]:
next_cost = abs(points[point][0] - points[next_point][0]) + abs(points[point][1] - points[next_point][1])
if next_cost < minDist[next_point]:
minDist[next_point] = next_cost
heapq.heappush(heap, (next_cost, next_point))
return totalCostimport java.util.*;
class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
Queue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
boolean[] inMST = new boolean[n];
int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0;
pq.offer(new int[]{0, 0}); // {cost, index}
int totalCost = 0;
while (!pq.isEmpty()) {
int[] edge = pq.poll();
int weight = edge[0], u = edge[1];
if (inMST[u]) continue;
inMST[u] = true;
totalCost += weight;
for (int v = 0; v < n; v++) {
if (!inMST[v]) {
int dist = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
if (dist < minDist[v]) {
minDist[v] = dist;
pq.offer(new int[]{dist, v});
}
}
}
}
return totalCost;
}
}#include <vector>
#include <unordered_set>
#include <queue>
#include <utility>
#include <functional>
#include <cmath>
using namespace std;
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size();
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> minDist(n, INT_MAX);
vector<bool> inMST(n, false);
int totalCost = 0;
minDist[0] = 0;
pq.push({0, 0}); // {dist, point}
while (!pq.empty()) {
auto [dist, curr] = pq.top();
pq.pop();
if (inMST[curr]) continue;
inMST[curr] = true;
totalCost += dist;
for (int next = 0; next < n; ++next) {
if (!inMST[next]) {
int nextDist = abs(points[curr][0] - points[next][0]) + abs(points[curr][1] - points[next][1]);
if (nextDist < minDist[next]) {
minDist[next] = nextDist;
pq.push({nextDist, next});
}
}
}
}
return totalCost;
}
};var minCostConnectPoints = function(points) {
const n = points.length;
const minDist = new Array(n).fill(Infinity);
const inMST = new Array(n).fill(false);
minDist[0] = 0;
const pq = new MinPriorityQueue({ priority: x => x[0] });
pq.enqueue([0, 0]);
let totalCost = 0;
while (!pq.isEmpty()) {
const [cost, u] = pq.dequeue().element;
if (inMST[u]) continue;
inMST[u] = true;
totalCost += cost;
for (let v = 0; v < n; v++) {
if (!inMST[v]) {
const dist = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
if (dist < minDist[v]) {
minDist[v] = dist;
pq.enqueue([dist, v]);
}
}
}
}
return totalCost;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXN 1000
int minCostConnectPoints(int** points, int pointsSize, int* pointsColSize) {
int n = pointsSize;
int minCost = 0;
int visited[MAXN] = {0};
int minWeight[MAXN];
for (int i = 1; i < n; i++) {
minWeight[i] = INT_MAX;
}
minWeight[0] = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && (u == -1 || minWeight[j] < minWeight[u])) {
u = j;
}
}
visited[u] = 1;
minCost += minWeight[u];
for (int v = 0; v < n; v++) {
if (!visited[v]) {
int dist = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]);
if (dist < minWeight[v]) {
minWeight[v] = dist;
}
}
}
}
return minCost;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinCostConnectPoints(int[][] points) {
int n = points.Length;
int[] minDist = new int[n];
bool[] inMST = new bool[n];
PriorityQueue<(int, int), int> pq = new();
Array.Fill(minDist, int.MaxValue);
minDist[0] = 0;
pq.Enqueue((0, 0), 0);
int totalCost = 0;
while (pq.TryDequeue(out var edge, out int cost)) {
int u = edge.Item2;
if (inMST[u]) continue;
inMST[u] = true;
totalCost += cost;
for (int v = 0; v < n; v++) {
if (!inMST[v]) {
int dist = Math.Abs(points[u][0] - points[v][0]) + Math.Abs(points[u][1] - points[v][1]);
if (dist < minDist[v]) {
minDist[v] = dist;
pq.Enqueue((dist, v), dist);
}
}
}
}
return totalCost;
}
}This Python solution uses a min-heap for Prim's algorithm, ensuring that the edge being considered is of the minimal weight at all times. It maintains arrays to track visited nodes and minimum weights for edges, updating and expanding the MST iteratively. The resulting solution provides the overall minimum cost to connect the set of given points.
Time complexity involves heap operations, yielding O(n^2 log n), with space complexity O(n) for storing state across nodes and a min-heap for edges.
Approach 3: Default Approach
function minCostConnectPoints(points: number[][]): number {
const n = points.length;
const g: number[][] = Array(n)
.fill(0)
.map(() => Array(n).fill(0));
const dist: number[] = Array(n).fill(1 << 30);
const vis: boolean[] = Array(n).fill(false);
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 t = Math.abs(x1 - x2) + Math.abs(y1 - y2);
g[i][j] = t;
g[j][i] = t;
}
}
let ans = 0;
dist[0] = 0;
for (let i = 0; i < n; ++i) {
let j = -1;
for (let k = 0; k < n; ++k) {
if (!vis[k] && (j === -1 || dist[k] < dist[j])) {
j = k;
}
}
vis[j] = true;
ans += dist[j];
for (let k = 0; k < n; ++k) {
if (!vis[k]) {
dist[k] = Math.min(dist[k], g[j][k]);
}
}
}
return ans;
}func minCostConnectPoints(points [][]int) (ans int) {
n := len(points)
g := make([][]int, n)
vis := make([]bool, n)
dist := make([]int, n)
for i := range g {
g[i] = make([]int, n)
dist[i] = 1 << 30
}
for i := range g {
x1, y1 := points[i][0], points[i][1]
for j := i + 1; j < n; j++ {
x2, y2 := points[j][0], points[j][1]
t := abs(x1-x2) + abs(y1-y2)
g[i][j] = t
g[j][i] = t
}
}
dist[0] = 0
for i := 0; i < n; i++ {
j := -1
for k := 0; k < n; k++ {
if !vis[k] && (j == -1 || dist[k] < dist[j]) {
j = k
}
}
vis[j] = true
ans += dist[j]
for k := 0; k < n; k++ {
if !vis[k] {
dist[k] = min(dist[k], g[j][k])
}
}
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Kruskal's Algorithm with Union-Find | Just like in other languages, the time complexity is |
| Approach 2: Prim's Algorithm | Time complexity involves heap operations, yielding |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Kruskal's Algorithm with Union-Find | O(n^2 log n) | O(n^2) | When you want a straightforward MST approach using sorted edges and Disjoint Set Union. |
| Prim's Algorithm (Array-based) | O(n^2) | O(n) | Best for dense graphs like this one where every pair of nodes can connect. |
Frequently asked questions
Is Min Cost to Connect All Points easy or hard?
LeetCode classifies the problem as Medium difficulty. The main challenge is recognizing that the points form a complete graph and that the task reduces to building a Minimum Spanning Tree using algorithms such as Prim or Kruskal.
Min Cost to Connect All Points Python/Java solution
Most implementations use either Kruskal with Union-Find or Prim's algorithm. Python solutions often implement Prim with a distance array for O(n^2) complexity, while Java and C++ versions may use either Prim or Kruskal depending on preference.
How to solve Min Cost to Connect All Points in O(n^2)?
Use Prim's algorithm with a distance array. Start with any point, track the minimum cost needed to connect each remaining point, and repeatedly add the closest unvisited point to the MST. Update distances using Manhattan distance calculations. This avoids building all edges and achieves O(n^2) time.
What is the best approach for Min Cost to Connect All Points?
Prim's algorithm is typically the best approach. The graph formed by all points is dense because every pair can connect, so generating all edges for Kruskal is unnecessary. Prim's algorithm computes distances on demand and runs in O(n^2) time with O(n) space, making it efficient and simpler to implement.
Is Min Cost to Connect All Points asked at Google/Amazon/Meta?
Min Cost to Connect All Points appears frequently in interviews at companies that test graph fundamentals such as Amazon, Google, Meta, and Microsoft. It evaluates understanding of Minimum Spanning Tree algorithms like Kruskal and Prim along with union-find data structures.
What data structure is used in Min Cost to Connect All Points?
Common structures include Union-Find (Disjoint Set Union) for Kruskal's algorithm and arrays or priority queues for Prim's algorithm. These help track connected components or the minimum edge needed to expand the current Minimum Spanning Tree.
What is the time complexity of Min Cost to Connect All Points?
The optimal implementation using Prim's algorithm runs in O(n^2) time and O(n) space. A Kruskal-based solution requires generating all edges between points, which leads to O(n^2 log n) time due to sorting the edge list.