Minimize manhattan distances

Array Math Geometry Sorting Ordered Set

32.8% acceptance

Feb 23, 2026

186

You are given an array points representing integer coordinates of some points on a 2D plane, where points[i] = [xi, yi]. The distance between two points is defined as their Manhattan distance. Return the minimum possible value for maximum distance between any two points by removing exactly one point.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_distance(points: Vec<Vec<i32>>) -> i32 {
    let n = points.len();
    // Manhattan distance trick: |x1-x2|+|y1-y2| = max(|(x+y)1-(x+y)2|, |(x-y)1-(x-y)2|)
    // Max manhattan dist over all pairs = max(max(x+y)-min(x+y), max(x-y)-min(x-y))
    let mut sum: Vec<(i32, usize)> = points.iter().enumerate().map(|(i, p)| (p[0] + p[1], i)).collect();
    let mut diff: Vec<(i32, usize)> = points.iter().enumerate().map(|(i, p)| (p[0] - p[1], i)).collect();
    sum.sort_unstable();
    diff.sort_unstable();

    // Candidates to remove: the 4 extreme-achieving indices
    let candidates = [sum[0].1, sum[n - 1].1, diff[0].1, diff[n - 1].1];

    let max_dist = |exclude: usize| -> i32 {
      let s_max = if sum[n - 1].1 == exclude { sum[n - 2].0 } else { sum[n - 1].0 };
      let s_min = if sum[0].1 == exclude { sum[1].0 } else { sum[0].0 };
      let d_max = if diff[n - 1].1 == exclude { diff[n - 2].0 } else { diff[n - 1].0 };
      let d_min = if diff[0].1 == exclude { diff[1].0 } else { diff[0].0 };
      (s_max - s_min).max(d_max - d_min)
    };

    candidates.iter().map(|&c| max_dist(c)).min().unwrap()
  }
}