Log inSign up
mediumLeetCodeNot Started

Min Cost to Connect All Points

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

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.

Constraints:

  • 1 <= points.length <= 1000
  • -106 <= xi, yi <= 106
  • All pairs (xi, yi) are distinct.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate geometric network connection problems into Minimum Spanning Tree (MST) models.
  • Compare dense Prim's algorithm vs. min-heap Prim's vs. Kruskal's algorithm on complete graphs.
  • Implement Prim's algorithm using a minDist tracker to achieve O(V2) time and O(V) space without allocating all E = O(V2) edges.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Whenever you need to connect all vertices in a metric space (2D points) with minimal total cost and no cycles, model it as an MST problem. If all pairs can connect, the graph is complete (E = V2). Kruskal's requires sorting O(V2) edges (O(V2 log V)), whereas dense Prim's inspects all nodes sequentially in O(V2) time with O(V) memory.

1. Kruskal's Algorithm with Explicit Edge Generation

Intuition

Generate all possible edges between every pair of points (u, v) with Manhattan weight |x_u - x_v| + |y_u - y_v|. There are V(V-1)/2 edges. Sort all edges ascending by weight and use Disjoint Set Union (DSU) to greedily pick non-cycle-forming edges until V - 1 edges have been included.

Algorithm

  1. Create an edge list containing all pairs (i, j) with weight |x_i - x_j| + |y_i - y_j| for 0 <= i < j < n.
  2. Sort the edge list in ascending order of weight.
  3. Initialize DSU with n elements.
  4. Iterate through sorted edges; for each edge (u, v, w), check if find(u) != find(v). If true, union them, accumulate w, and increment edge count.
  5. Stop once n - 1 edges are added and return the total cost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4#include <numeric>
5#include <algorithm>
6
7struct Edge {
8 int u, v, weight;
9 bool operator<(const Edge& other) const {
10 return weight < other.weight;
11 }
12};
13
14class DSU {
15 std::vector<int> parent;
16public:
17 DSU(int n) : parent(n) {
18 std::iota(parent.begin(), parent.end(), 0);
19 }
20 int find(int i) {
21 if (parent[i] == i) return i;
22 return parent[i] = find(parent[i]);
23 }
24 bool unite(int i, int j) {
25 int rootI = find(i);
26 int rootJ = find(j);
27 if (rootI != rootJ) {
28 parent[rootI] = rootJ;
29 return true;
30 }
31 return false;
32 }
33};
34
35int minCostConnectPoints(std::vector<std::vector<int>>& points) {
36 int n = points.size();
37 std::vector<Edge> edges;
38 for (int i = 0; i < n; ++i) {
39 for (int j = i + 1; j < n; ++j) {
40 int dist = std::abs(points[i][0] - points[j][0]) + std::abs(points[i][1] - points[j][1]);
41 edges.push_back({i, j, dist});
42 }
43 }
44 std::sort(edges.begin(), edges.end());
45 DSU dsu(n);
46 int totalCost = 0, count = 0;
47 for (const auto& edge : edges) {
48 if (dsu.unite(edge.u, edge.v)) {
49 totalCost += edge.weight;
50 if (++count == n - 1) break;
51 }
52 }
53 return totalCost;
54}
55
56int main() {
57 std::vector<std::vector<int>> points = {{0,0},{2,2},{3,10},{5,2},{7,0}};
58 std::cout << "Min Cost: " << minCostConnectPoints(points) << std::endl;
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(V^2 log V) where V is points.length. Generating V(V-1)/2 edges and sorting them dominates.
  • Space complexity: O(V^2) auxiliary memory to store all V(V-1)/2 edges in an explicit edge list.

2. Prim's Algorithm with Min-Heap

Intuition

Instead of generating all O(V2) edges upfront, grow the MST starting from node 0. Use a min-heap to always pop the unvisited vertex with the minimum connecting edge to any node currently in the MST. Once added, push all edges connecting to remaining unvisited vertices into the priority queue.

Algorithm

  1. Initialize a boolean array visited of size n, set visited[0] = false (or initially false for all).
  2. Push (cost = 0, node = 0) into min-heap.
  3. While min-heap is not empty and visited count < n:
  4. Pop (cost, u). If visited[u] is true, continue.
  5. Mark visited[u] = true, add cost to totalCost, increment visited counter.
  6. For every other vertex v where !visited[v]:
  7. Compute dist = |points[u][0] - points[v][0]| + |points[u][1] - points[v][1]| and push (dist, v) into heap.
  8. Return totalCost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <cmath>
5
6int minCostConnectPoints(std::vector<std::vector<int>>& points) {
7 int n = points.size();
8 std::vector<bool> visited(n, false);
9 // pair: (cost, node)
10 std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
11 pq.push({0, 0});
12 int totalCost = 0, connected = 0;
13
14 while (!pq.empty() && connected < n) {
15 auto [cost, u] = pq.top();
16 pq.pop();
17 if (visited[u]) continue;
18 visited[u] = true;
19 totalCost += cost;
20 connected++;
21
22 for (int v = 0; v < n; ++v) {
23 if (!visited[v]) {
24 int dist = std::abs(points[u][0] - points[v][0]) + std::abs(points[u][1] - points[v][1]);
25 pq.push({dist, v});
26 }
27 }
28 }
29 return totalCost;
30}
31
32int main() {
33 std::vector<std::vector<int>> points = {{0,0},{2,2},{3,10},{5,2},{7,0}};
34 std::cout << "Min Cost: " << minCostConnectPoints(points) << std::endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(V^2 log V) in the worst case because up to O(V^2) elements can be pushed into the min-heap.
  • Space complexity: O(V^2) for the priority queue storing edges, but avoids generating all edges before sorting.

3. Dense Prim's Algorithm (O(V^2) Time, O(V) Space)

Intuition

Because the graph is complete (E = V(V-1)/2), a min-heap incurs an extra O(log V) factor on every edge update. Instead, use an array minDist of size V where minDist[i] stores the shortest distance from node i to the currently formed tree. In each step, linearly find the unvisited node with minimal minDist, add it to the MST, and update minDist for all remaining unvisited nodes. This takes O(V2) time and only O(V) auxiliary space with zero heap overhead.

Algorithm

  1. Initialize an array minDist of size n filled with infinity, set minDist[0] = 0.
  2. Initialize an array visited of size n filled with false.
  3. Loop n times (once for each vertex):
  4. Scan all vertices to find the unvisited vertex u with minimum minDist[u].
  5. Mark visited[u] = true, add minDist[u] to totalCost.
  6. For every other vertex v with !visited[v]:
  7. dist = |points[u][0] - points[v][0]| + |points[u][1] - points[v][1]|
  8. minDist[v] = min(minDist[v], dist)
  9. Return totalCost.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4#include <climits>
5#include <algorithm>
6
7int minCostConnectPoints(std::vector<std::vector<int>>& points) {
8 int n = points.size();
9 std::vector<int> minDist(n, INT_MAX);
10 std::vector<bool> visited(n, false);
11 minDist[0] = 0;
12 int totalCost = 0;
13
14 for (int step = 0; step < n; ++step) {
15 int u = -1;
16 for (int i = 0; i < n; ++i) {
17 if (!visited[i] && (u == -1 || minDist[i] < minDist[u])) {
18 u = i;
19 }
20 }
21
22 visited[u] = true;
23 totalCost += minDist[u];
24
25 for (int v = 0; v < n; ++v) {
26 if (!visited[v]) {
27 int dist = std::abs(points[u][0] - points[v][0]) + std::abs(points[u][1] - points[v][1]);
28 if (dist < minDist[v]) {
29 minDist[v] = dist;
30 }
31 }
32 }
33 }
34
35 return totalCost;
36}
37
38int main() {
39 std::vector<std::vector<int>> points = {{0,0},{2,2},{3,10},{5,2},{7,0}};
40 std::cout << "Optimal Min Cost: " << minCostConnectPoints(points) << std::endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(V^2) where V is the number of points. In each of the V iterations, finding the minimum node takes O(V) and updating neighbors takes O(V).
  • Space complexity: O(V) auxiliary space for visited and minDist arrays. No edge lists or heaps stored.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Kruskal's AlgorithmO(V^2 log V)O(V^2)Conceptually direct; sorts edge list and leverages DSU disjoint sets.Allocating and sorting V(V-1)/2 edges causes large memory consumption and slow heap allocations.
2.Prim's with Min-HeapO(V^2 log V)O(V^2)Grows tree incrementally without creating all edges upfront.Min-heap contains duplicate vertex entries and incurs logarithmic overhead per pushed edge.
3.Dense Prim's (Array-based)OptimalO(V^2)O(V)Optimal runtime and minimal O(V) auxiliary space; zero dynamic memory overhead, cache-friendly linear scans.Only optimal for dense graphs where E is close to V2.

Common Pitfalls & Crucial Edge Cases

Allocating an explicit NxN adjacency matrix in memory.

For N = 1000, 1000x1000 is 1 million ints, which wastes memory. Calculate Manhattan distance on-the-fly inside the inner loop.

Using Euclidean distance instead of Manhattan distance.

The problem explicitly states cost is Manhattan distance: |x1 - x2| + |y1 - y2|, not sqrt((x1-x2)^2 + (y1-y2)^2).

Pushing nodes to min-heap without tracking visited status on extraction.

Nodes can be inserted multiple times with different shorter keys; always skip already visited nodes when popped.

Crucial Edge Cases to Validate:

  • n = 1 (Single point) — Zero edges needed; loop runs 1 iteration, cost remains 0.
  • Points in a straight line or colinear coordinates — Manhattan distances naturally preserve metric triangle inequality; dense Prim's will connect adjacent collinear points with optimal minimal edges.
  • Duplicate coordinate values in one dimension (e.g. all same x or same y) — Standard absolute difference correctly evaluates to 1D distances without any special branching.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the graph density up front: 'Since any point can connect to any other point, this is a complete graph with E = V(V-1)/2 edges.'
  2. Highlight that while Kruskal's is great for sparse graphs (E << V2), Prim's with an array is the textbook optimal choice for dense graphs (E = Theta(V2)) yielding O(V2) time and O(V) space.
  3. Mention that Euclidean MST can be solved in O(V log V) using Delaunay triangulation, but Manhattan MST on arbitrary coordinates generally remains O(V2) without specialized geometric range query trees.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is dense Prim's algorithm O(V2) faster than heap-based Prim's O(V2 log V) on this problem?

2.What is the space complexity of dense Prim's algorithm for connecting V points?

3.If points length is 1, what is the minimum cost to connect all points?

Back to DSA Sheet