Minimum Cost to Connect All Points

Share

Given points as (x,y) coordinates, connect all points using minimum total Manhattan distance. Each point connects to exactly one path (minimum spanning tree).

Example 1
Input: [[0,0],[2,2],[3,10],[5,2],[7,0]] → Output: 20
Example 2
Input: [[3,12],[-2,5],[-4,1]] → Output: 18

Solution Approach

Prim's MST algorithm: start from any node, greedily add the closest unvisited node.

  • dist[] tracks minimum cost to include each node in MST.
  • For each of n-1 steps: pick min-dist unvisited node u, mark visited.
  • Update dist[v] for all unvisited v using Manhattan distance.
  • Sum all picked distances.
Java
class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        java.util.Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        int total = 0;
        for (int i = 0; i < n; i++) {
            int u = -1;
            for (int j = 0; j < n; j++) if (!visited[j] && (u == -1 || dist[j] < dist[u])) u = j;
            visited[u] = true;
            total += dist[u];
            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]);
                    dist[v] = Math.min(dist[v], d);
                }
            }
        }
        return total;
    }
}
  • Time Complexity: O(N^2)
  • Space Complexity: O(N)