Maximize the distance between points on a square

Array Math Binary Search Geometry Sorting

23.6% acceptance

Feb 25, 2026

You are given an integer side, representing the edge length of a square with corners at (0, 0), (0, side), (side, 0), and (side, side) on a Cartesian plane. You are also given a positive integer k and a 2D integer array points, where points[i] = [xi, yi] represents the coordinate of a point lying on the boundary of the square. You need to select k elements among points such that the minimum Manhattan distance between any two points is maximized. Return the maximum possible minimum Manhattan distance between the selected k points. The Manhattan Distance between two cells (xi, yi) and (xj, yj) is |xi - xj| + |yi - yj|.

Solution

Rust

Time O(n³)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_distance(side: i32, points: Vec<Vec<i32>>, k: i32) -> i32 {
    let s = side as i64;
    let k = k as usize;
    let mut pos: Vec<i64> = points.iter().map(|p| {
      let (x, y) = (p[0] as i64, p[1] as i64);
      if y == 0 { x }
      else if x == s { s + y }
      else if y == s { 3 * s - x }
      else { 4 * s - y }
    }).collect();
    pos.sort_unstable();
    let n = pos.len();
    let perim = 4 * s;

    // Virtual doubled array: index i → pos[i] for i<n, pos[i-n]+perim for i>=n.
    // Avoids allocating a 2n Vec; binary search uses the same O(log n) cost.
    let get = |i: usize| -> i64 {
      if i < n { pos[i] } else { pos[i - n] + perim }
    };

    // For each starting index, greedily pick k points with binary search → O(n·k·log n) per check.
    let check = |d: i64| -> bool {
      for start in 0..n {
        let mut idx = start;
        let mut ok = true;
        for _ in 1..k {
          let target = get(idx) + d;
          // Binary-search first position >= target in [idx+1, start+n)
          let mut lo = idx + 1;
          let mut hi = start + n;
          while lo < hi {
            let mid = lo + (hi - lo) / 2;
            if get(mid) < target { lo = mid + 1; } else { hi = mid; }
          }
          if lo < start + n {
            idx = lo;
          } else {
            ok = false;
            break;
          }
        }
        if ok {
          // Wrap gap: from get(idx) back to get(start) (full circle)
          if get(start) + perim - get(idx) >= d {
            return true;
          }
        }
      }
      false
    };

    let mut lo = 0i64;
    let mut hi = perim / k as i64;
    while lo < hi {
      let mid = (lo + hi + 1) / 2;
      if check(mid) { lo = mid; } else { hi = mid - 1; }
    }
    lo as i32
  }
}