Min cost to connect all points

Array Union-Find Graph Theory Minimum Spanning Tree

70.4% acceptance

Feb 25, 2026

5588

144

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

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_cost_connect_points(points: Vec<Vec<i32>>) -> i32 {
    // Prim's algorithm
    let n = points.len();
    if n == 1 {
      return 0;
    }
    let mut in_mst = vec![false; n];
    let mut min_dist = vec![i32::MAX; n];
    min_dist[0] = 0;
    let mut total = 0;

    for _ in 0..n {
      // Find the vertex with minimum distance not in MST
      let u = (0..n)
        .filter(|&i| !in_mst[i])
        .min_by_key(|&i| min_dist[i])
        .unwrap();
      in_mst[u] = true;
      total += min_dist[u];

      // Update distances
      for v in 0..n {
        if !in_mst[v] {
          let d = (points[u][0] - points[v][0]).abs() + (points[u][1] - points[v][1]).abs();
          if d < min_dist[v] {
            min_dist[v] = d;
          }
        }
      }
    }
    total
  }
}