Course4all
Join us on telegram
Home/dsa/Graphs/Minimum Cost to Connect All Points

Minimum Cost to Connect All Points

Master this topic with zero to advance depth.

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;
    }
}
← Previous QuestionAlien Dictionary
Next Question →Swim in Rising Water