Skip to main content
CodePeetCodePeet
CodePeet 250

Min Cost to Connect All Points

MEDIUMProblemSolveExternal Links

Description

You are given a list of points on a 2D plane, where points[i] = [xᵢ, yᵢ] represents a distinct point.

The cost of connecting two points [xᵢ, yᵢ] and [xⱼ, yⱼ] is the Manhattan distance between them:

cost = |xᵢ - xⱼ| + |yᵢ - yⱼ|

Return the minimum total cost to connect all points such that there is exactly one path between every pair of points. In other words, you need to form a tree (called a spanning tree) that includes every point, and the sum of edge costs in that tree is minimized.

This is a classic Minimum Spanning Tree (MST) problem. You must choose exactly n - 1 edges from all possible connections to link all n points together with the lowest total Manhattan distance.

Four points on a 2D plane with Manhattan distances labeled on edges, and the MST edges highlighted in green.
Four points on a 2D plane with Manhattan distances labeled on edges, and the MST edges highlighted in green.

Examples

Example 1

Input: points = [[0,0],[2,2],[3,10],[5,2]]

Output: 16

Explanation: There are 4 points and 6 possible connections:

  • P0↔P1: |0−2| + |0−2| = 4
  • P0↔P2: |0−3| + |0−10| = 13
  • P0↔P3: |0−5| + |0−2| = 7
  • P1↔P2: |2−3| + |2−10| = 9
  • P1↔P3: |2−5| + |2−2| = 3
  • P2↔P3: |3−5| + |10−2| = 10

The minimum spanning tree uses edges: P1↔P3 (cost 3) + P0↔P1 (cost 4) + P1↔P2 (cost 9) = 16. Every point is reachable from every other point through this tree.

Example 2

Input: points = [[0,0],[2,2],[3,3],[2,4],[4,2]]

Output: 10

Explanation: With 5 points, there are 10 possible edges. Many pairs have Manhattan distance 2 (e.g., P1↔P2, P1↔P3, P1↔P4, P2↔P3, P2↔P4). The MST selects 4 edges totaling cost 10: three edges of cost 2 connecting P1 to P2, P3, and P4, plus one edge of cost 4 connecting P0 to P1.

Example 3

Input: points = [[0,0]]

Output: 0

Explanation: With only one point, no connections are needed. The cost is 0.

Constraints

  • 1 ≤ points.length ≤ 1000
  • -10^6 ≤ xᵢ, yᵢ ≤ 10^6
  • All pairs (xᵢ, yᵢ) are distinct

Editorial

Brute Force - Kruskal's Algorithm

Intuition

Connecting all points with minimum total cost is a Minimum Spanning Tree (MST) problem. Think of each point as a city and each possible connection as a potential road. We want to build exactly n - 1 roads so every city is reachable, while minimizing total road-building cost.

The most straightforward MST algorithm is Kruskal's Algorithm. The idea is greedy and intuitive:

  1. List every possible road (edge) between every pair of cities (points).
  2. Sort all roads from cheapest to most expensive.
  3. Go through the sorted list and add each road unless it would create a loop (cycle). A cycle means those cities are already connected — adding another road between them wastes money.

To detect cycles efficiently, we use a Union-Find (Disjoint Set Union) data structure. It groups points into connected components and can quickly answer: "Are these two points already in the same group?" If yes, skip the edge. If no, merge the two groups and add the edge cost.

Since every pair of n points can be connected, we have n(n-1)/2 potential edges. Sorting them takes O(n² log n) time, which dominates the algorithm.

Step-by-Step Explanation

Let's trace through Example 1: points = [[0,0],[2,2],[3,10],[5,2]].

Points: P0=(0,0), P1=(2,2), P2=(3,10), P3=(5,2).

Step 1: Compute Manhattan distances for all 6 pairs:

  • P0↔P1 = 4, P0↔P2 = 13, P0↔P3 = 7
  • P1↔P2 = 9, P1↔P3 = 3, P2↔P3 = 10

Step 2: Sort edges by cost: [(P1,P3,3), (P0,P1,4), (P0,P3,7), (P1,P2,9), (P2,P3,10), (P0,P2,13)].

Step 3: Initialize Union-Find. Each point is its own component: {P0}, {P1}, {P2}, {P3}.

Step 4: Process edge (P1,P3) cost 3. Are P1 and P3 in the same component? No. Union them → {P1,P3}. Add to MST. Total = 3.

Step 5: Process edge (P0,P1) cost 4. P0 is in {P0}, P1 is in {P1,P3}. Different components → Union. Now {P0,P1,P3}. Total = 7.

Step 6: Process edge (P0,P3) cost 7. P0 and P3 are both in {P0,P1,P3}. Same component → SKIP! Adding this edge would create a cycle P0→P1→P3→P0.

Step 7: Process edge (P1,P2) cost 9. P1 is in {P0,P1,P3}, P2 is in {P2}. Different → Union. Now all 4 points connected. Total = 16. We have n−1 = 3 edges — done!

Step 8: MST complete. Total cost = 3 + 4 + 9 = 16.

Kruskal's Algorithm — Sorting Edges and Building MST — Watch how Kruskal's algorithm processes edges from cheapest to most expensive, adding each edge only if it connects two separate components.

Algorithm

  1. Compute Manhattan distance for every pair of points → n(n-1)/2 edges.
  2. Sort all edges by cost (ascending).
  3. Initialize Union-Find: each point is its own component.
  4. Iterate through sorted edges:
    a. For each edge (u, v, cost): if find(u) ≠ find(v) (different components), union them and add cost to the total.
    b. Stop early once n - 1 edges have been added.
  5. Return the total cost.

Code

class Solution {
public:
    vector<int> parent, rnk;

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rnk[px] < rnk[py]) swap(px, py);
        parent[py] = px;
        if (rnk[px] == rnk[py]) rnk[px]++;
        return true;
    }

    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        parent.resize(n);
        rnk.resize(n, 0);
        for (int i = 0; i < n; i++) parent[i] = i;

        vector<tuple<int,int,int>> edges;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int cost = abs(points[i][0] - points[j][0])
                         + abs(points[i][1] - points[j][1]);
                edges.push_back({cost, i, j});
            }
        }

        sort(edges.begin(), edges.end());

        int totalCost = 0, edgesUsed = 0;
        for (auto& [cost, u, v] : edges) {
            if (unite(u, v)) {
                totalCost += cost;
                if (++edgesUsed == n - 1) break;
            }
        }
        return totalCost;
    }
};
class Solution:
    def minCostConnectPoints(self, points: list[list[int]]) -> int:
        n = len(points)
        parent = list(range(n))
        rank = [0] * n

        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            px, py = find(x), find(y)
            if px == py:
                return False
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True

        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()

        total_cost = 0
        edges_used = 0
        for cost, u, v in edges:
            if union(u, v):
                total_cost += cost
                edges_used += 1
                if edges_used == n - 1:
                    break

        return total_cost
class Solution {
    int[] parent, rank;

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        int[][] edges = new int[n * (n - 1) / 2][3];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int cost = Math.abs(points[i][0] - points[j][0])
                         + Math.abs(points[i][1] - points[j][1]);
                edges[idx++] = new int[]{cost, i, j};
            }
        }

        Arrays.sort(edges, (a, b) -> a[0] - b[0]);

        int totalCost = 0, edgesUsed = 0;
        for (int[] edge : edges) {
            if (union(edge[1], edge[2])) {
                totalCost += edge[0];
                if (++edgesUsed == n - 1) break;
            }
        }
        return totalCost;
    }
}

Complexity Analysis

Time Complexity: O(n² log n)

Generating all edges takes O(n²) since we enumerate every pair. Sorting the n(n-1)/2 ≈ O(n²) edges costs O(n² log(n²)) = O(n² log n). Processing edges with Union-Find (with path compression and union by rank) is nearly O(n²) amortized. The sorting step dominates, giving O(n² log n) overall. For n = 1000, this is roughly 10^7 — fast enough but not the tightest.

Space Complexity: O(n²)

We store all n(n-1)/2 edges explicitly. Each edge is a tuple of (cost, u, v). The Union-Find arrays use O(n) space. Total: O(n²) dominated by the edge list.

Why This Approach Is Not Efficient

Kruskal's algorithm works correctly but carries two penalties for dense graphs (graphs where every node connects to every other node, like our complete point graph):

  1. Sorting overhead: We generate O(n²) edges and sort them, costing O(n² log n). For n = 1000, that is about 10^7 comparisons just for sorting. The log factor is unnecessary — we can avoid it entirely.

  2. Memory overhead: Storing all O(n²) edges requires O(n²) space. For n = 1000, that is ~500,000 edge tuples. We can avoid materializing these edges altogether.

The key insight: Kruskal's is designed for sparse graphs (few edges). For dense graphs (many edges), Prim's algorithm is fundamentally better because it works node-by-node rather than edge-by-edge. Instead of sorting all edges upfront, Prim's considers only the immediate neighborhood of the growing MST and can find the cheapest connection in O(n) time per step — no sorting needed.

For our complete graph, Prim's without a heap runs in O(n²) time with only O(n) space, eliminating both the log factor and the quadratic memory.

Optimal Approach - Prim's Algorithm (Dense Graph)

Intuition

Prim's algorithm builds the MST by growing a connected tree one node at a time, always picking the cheapest available connection to an unvisited node.

Imagine you are building a railway network between cities. You start at one city. At each step, you look at all cities not yet connected to your railway and ask: "Which unconnected city can I reach most cheaply from my current network?" You build the cheapest rail link, connect that city, and repeat until every city is on the network.

The implementation maintains a dist[] array where dist[j] stores the minimum Manhattan distance from point j to any point currently in the MST. Initially, all distances are infinity except the starting point (distance 0).

In each round:

  1. Select the unvisited point with the smallest dist value.
  2. Add that point to the MST and add dist[point] to the total cost.
  3. Update dist for all remaining unvisited points: for each, check if the newly added point is closer than the previously known best connection.

Because the graph is dense (every point connects to every other), we scan all n points to find the minimum — this linear scan takes O(n) per iteration, and we do n iterations, giving O(n²) total. No sorting, no heap, no edge storage. Just two arrays of size n.

This approach also computes Manhattan distances on the fly rather than pre-computing and storing them, reducing space from O(n²) to O(n).

Step-by-Step Explanation

Let's trace through Example 1: points = [[0,0],[2,2],[3,10],[5,2]].

Points: P0=(0,0), P1=(2,2), P2=(3,10), P3=(5,2).

Step 1: Initialize dist = [0, ∞, ∞, ∞]. Start from P0 (dist = 0). All nodes unvisited.

Step 2: Select unvisited node with minimum dist: P0 (dist = 0). Mark P0 as visited. Total cost += 0 = 0.

Step 3: Update distances from P0: dist[1] = min(∞, 4) = 4, dist[2] = min(∞, 13) = 13, dist[3] = min(∞, 7) = 7. New dist = [0, 4, 13, 7].

Step 4: Select min unvisited: P1 (dist = 4). Mark P1 as visited. Total cost += 4 = 4. MST edge: P0↔P1.

Step 5: Update from P1: dist[2] = min(13, 9) = 9 (P1 is closer to P2 than P0 was!), dist[3] = min(7, 3) = 3 (P1 is much closer to P3!). New dist = [0, 4, 9, 3].

Step 6: Select min unvisited: P3 (dist = 3). It was 7 from P0, but P1 reduced it to 3. Mark P3 visited. Total += 3 = 7. MST edge: P1↔P3.

Step 7: Update from P3: dist[2] = min(9, 10) = 9. P3 is further from P2 than P1, so no improvement.

Step 8: Select min unvisited: P2 (dist = 9). Only one left. Mark P2 visited. Total += 9 = 16. MST edge: P1↔P2.

Step 9: All nodes visited. Total cost = 0 + 4 + 3 + 9 = 16.

Prim's Algorithm — Growing the MST Node by Node — Watch how Prim's algorithm greedily selects the nearest unvisited point at each step, updating distance estimates as the MST grows.

Algorithm

  1. Initialize dist[0] = 0 and dist[j] = ∞ for all other points. Initialize visited[] as all false.
  2. Set totalCost = 0.
  3. Repeat n times:
    a. Find the unvisited node u with the smallest dist[u]. (Linear scan: O(n))
    b. Mark u as visited. Add dist[u] to totalCost.
    c. Update distances: for every unvisited node j, compute cost = |x_u - x_j| + |y_u - y_j|. Set dist[j] = min(dist[j], cost). Distances are computed on the fly — no need to store the full adjacency matrix.
  4. Return totalCost.

Code

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size();
        vector<int> dist(n, INT_MAX);
        vector<bool> visited(n, false);

        dist[0] = 0;
        int totalCost = 0;

        for (int i = 0; i < n; i++) {
            // Find unvisited node with minimum distance
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                    u = j;
                }
            }

            visited[u] = true;
            totalCost += dist[u];

            // Update distances for all unvisited nodes
            for (int j = 0; j < n; j++) {
                if (!visited[j]) {
                    int cost = abs(points[u][0] - points[j][0])
                             + abs(points[u][1] - points[j][1]);
                    dist[j] = min(dist[j], cost);
                }
            }
        }

        return totalCost;
    }
};
class Solution:
    def minCostConnectPoints(self, points: list[list[int]]) -> int:
        n = len(points)
        dist = [float('inf')] * n
        visited = [False] * n

        dist[0] = 0
        total_cost = 0

        for _ in range(n):
            # Find unvisited node with minimum distance
            u = -1
            for j in range(n):
                if not visited[j] and (u == -1 or dist[j] < dist[u]):
                    u = j

            visited[u] = True
            total_cost += dist[u]

            # Update distances for all unvisited nodes
            for j in range(n):
                if not visited[j]:
                    cost = (abs(points[u][0] - points[j][0])
                          + abs(points[u][1] - points[j][1]))
                    dist[j] = min(dist[j], cost)

        return total_cost
class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        Arrays.fill(dist, Integer.MAX_VALUE);

        dist[0] = 0;
        int totalCost = 0;

        for (int i = 0; i < n; i++) {
            // Find unvisited node with minimum distance
            int u = -1;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                    u = j;
                }
            }

            visited[u] = true;
            totalCost += dist[u];

            // Update distances for all unvisited nodes
            for (int j = 0; j < n; j++) {
                if (!visited[j]) {
                    int cost = Math.abs(points[u][0] - points[j][0])
                             + Math.abs(points[u][1] - points[j][1]);
                    dist[j] = Math.min(dist[j], cost);
                }
            }
        }

        return totalCost;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times. In each iteration, finding the minimum unvisited node takes O(n) (linear scan), and updating distances for all unvisited nodes also takes O(n). Each iteration: O(n) + O(n) = O(n). Over n iterations: O(n²). No sorting step exists — the minimum is found by direct comparison. For n = 1000, this is exactly 10^6 operations, comfortably within time limits.

Space Complexity: O(n)

We use two arrays: dist[] of size n and visited[] of size n. Manhattan distances are computed on the fly (no adjacency matrix). Total: O(n). This is a dramatic improvement over Kruskal's O(n²) space, since we never store the edge list.