Min Cost to Connect All Points

Solutions

Kruskal's Algorithm

Time: O(N^2 log N)Space: O(N^2)

This solution uses Kruskal's algorithm to find the minimum spanning tree of the graph. The graph is represented as a set of edges, where each edge is a pair of points and the weight of the edge is the Manhattan distance between the two points. The algorithm sorts the edges by weight and then iterates over the sorted edges, adding each edge to the minimum spanning tree if it does not form a cycle with the edges already in the tree. The union-find data structure is used to keep track of the connected components of the graph.

function minCostConnectPoints(points) {
  let n = points.length;
  let edges = [];
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      let dist =
        Math.abs(points[i][0] - points[j][0]) +
        Math.abs(points[i][1] - points[j][1]);
      edges.push([dist, i, j]);
    }
  }
  edges.sort((a, b) => a[0] - b[0]);
  let parent = Array(n)
    .fill(0)
    .map((_, i) => i);
  let rank = Array(n).fill(0);
  let cost = 0;
  for (let [dist, u, v] of edges) {
    let rootU = find(parent, u);
    let rootV = find(parent, v);
    if (rootU !== rootV) {
      union(parent, rank, rootU, rootV);
      cost += dist;
    }
  }
  return cost;
}

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

function union(parent, rank, x, y) {
  let rootX = find(parent, x);
  let rootY = find(parent, y);
  if (rank[rootX] < rank[rootY]) {
    parent[rootX] = rootY;
  } else if (rank[rootX] > rank[rootY]) {
    parent[rootY] = rootX;
  } else {
    parent[rootY] = rootX;
    rank[rootX]++;
  }
}

Constraints:

Examples:

Solutions

Kruskal's Algorithm

Follow-up: