Course4all

Minimum Cost to Connect All Points

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Graphs.

Minimum Cost to Connect All Points

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [x_i, y_i].
The cost of connecting two points [x_i, y_i] and [x_j, y_j] is the manhattan distance between them: |x_i - x_j| + |y_i - y_j|.
Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Visual Representation

Points: [[0,0],[2,2],[3,10],[5,2],[7,0]] (3,10) | | (0,0)-(2,2)-(5,2)-(7,0) Min Cost to connect all points: 20
Hard

Examples

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Points are connected with total manhattan distance 20.
Approach 1

Level II: Intermediate (Kruskal's Algorithm)

Intuition

Kruskal's algorithm works by sorting all potential edges by weight and adding them one by one if they don't form a cycle (using Union-Find).

Thought Process

  1. Generate all N(N−1)/2N(N-1)/2 possible edges with their Manhattan distances.
  2. Sort edges by weight.
  3. Use Union-Find to process edges.
  4. Add edge to MST if endpoints are in different components.
  5. Stop when N−1N-1 edges are added.

Why it's Level II

It's very intuitive but slightly slower for dense graphs (O(Elog⁡E)=O(N2log⁡N)O(E \log E) = O(N^2 \log N)) compared to Prim's O(N2)O(N^2).
⏱ O(N^2 log N) - Due to sorting O(N^2) edges.💾 O(N^2) - To store all possible edges.

Detailed Dry Run

Points: [0,0], [2,2], [7,0]
  1. Edges: (0,1):4, (1,2):7, (0,2):7.
  2. Sort: [(0,1):4, (1,2):7, (0,2):7]
  3. Add (0,1): Cost=4. OK.
  4. Add (1,2): Cost=4+7=11. OK. Result: 11
java
class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int d = Math.abs(points[i][0]-points[j][0]) + Math.abs(points[i][1]-points[j][1]);
                edges.add(new int[]{d, i, j});
            }
        }
        Collections.sort(edges, (a, b) -> a[0] - b[0]);
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int res = 0, count = 0;
        for (int[] e : edges) {
            int rootU = find(e[1], parent), rootV = find(e[2], parent);
            if (rootU != rootV) {
                parent[rootU] = rootV;
                res += e[0]; count++;
                if (count == n - 1) break;
            }
        }
        return res;
    }
    private int find(int i, int[] p) {
        if (p[i] == i) return i;
        return p[i] = find(p[i], p);
    }
}
Approach 2

Level III: Optimal (Prim's Algorithm)

Intuition

For a dense graph (where every point connects to every other point), Prim's algorithm with a simple array is more efficient than Kruskal's or Prim's with a heap.

Thought Process

  1. Maintain a minDist array where minDist[i] is the shortest distance from the current MST to point i.
  2. Start with point 0, minDist[0] = 0.
  3. In each of NN iterations:
    • Find the unvisited point u with the smallest minDist.
    • Add minDist[u] to total cost.
    • Mark u as visited.
    • For every unvisited point v, update minDist[v] = min(minDist[v], dist(u, v)).

Pattern: Prim's on Dense Graph

⏱ O(N^2) - No priority queue needed for dense graphs.💾 O(N) - To store minDist and visited status.

Detailed Dry Run

Points: [0,0], [2,2], [3,10]
  • Start with node 0.
  • Node 0 to 1: dist 4. Node 0 to 2: dist 13.
  • Choose node 1 (min dist 4). Total = 4.
  • Node 1 to 2: dist 9. 9 < 13. Update minDist[2] = 9.
  • Choose node 2. Total = 4 + 9 = 13. Result: 13
java
class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length, res = 0, count = 0;
        boolean[] visited = new boolean[n];
        int[] minDist = new int[n];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[0] = 0;
        while (count < n) {
            int u = -1;
            for (int i = 0; i < n; i++) {
                if (!visited[i] && (u == -1 || minDist[i] < minDist[u])) u = i;
            }
            visited[u] = true; res += minDist[u]; count++;
            for (int v = 0; v < n; v++) {
                if (!visited[v]) {
                    int d = Math.abs(points[u][0]-points[v][0]) + Math.abs(points[u][1]-points[v][1]);
                    if (d < minDist[v]) minDist[v] = d;
                }
            }
        }
        return res;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionAlien Dictionary
Next Question →Swim in Rising Water