Minimum Cost to Connect Points (Kruskal)

Share

Given points as (x,y) coordinates, find the minimum total Manhattan distance to connect all points (minimum spanning tree using Kruskal's).

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

Generate all O(N^2) edges, sort by Manhattan distance, then use Kruskal's MST algorithm.

  • Generate all edges (i,j,dist) for i
  • Sort by distance.
  • Union-Find: add edge if it connects two different components.
  • Stop when n-1 edges are added.
Java
import java.util.*;

class Solution {
    int[] parent;
    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++)
                edges.add(new int[]{i,j,Math.abs(points[i][0]-points[j][0])+Math.abs(points[i][1]-points[j][1])});
        edges.sort((a,b)->a[2]-b[2]);
        parent = new int[n]; for (int i=0;i<n;i++) parent[i]=i;
        int total=0, used=0;
        for (int[] e : edges) {
            if (used==n-1) break;
            int pu=find(e[0]),pv=find(e[1]);
            if (pu!=pv) { parent[pu]=pv; total+=e[2]; used++; }
        }
        return total;
    }
    private int find(int x){return parent[x]==x?x:(parent[x]=find(parent[x]));}
}
  • Time Complexity: O(N^2 log N)
  • Space Complexity: O(N^2)