Best meeting point

Array Math Sorting Matrix

61.4% acceptance

Mar 31, 2026

1215

108

Given an m x n binary grid grid where each 1 marks the home of one friend, return the minimal total travel distance. The total travel distance is the sum of the distances between the houses of the friends and the meeting point. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_total_distance(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let mut rows = Vec::new();
    let mut cols = Vec::new();
    for i in 0..m {
      for j in 0..n {
        if grid[i][j] == 1 {
          rows.push(i as i32);
        }
      }
    }
    for j in 0..n {
      for i in 0..m {
        if grid[i][j] == 1 {
          cols.push(j as i32);
        }
      }
    }
    Self::min_dist_1d(&rows) + Self::min_dist_1d(&cols)
  }

  fn min_dist_1d(points: &[i32]) -> i32 {
    let mut sum = 0;
    let (mut i, mut j) = (0, points.len() - 1);
    while i < j {
      sum += points[j] - points[i];
      i += 1;
      j -= 1;
    }
    sum
  }
}