Maximum partition factor

Array Binary Search Depth-First Search Breadth-First Search Union-Find Graph Theory

31.1% acceptance

Feb 24, 2026

You are given a 2D integer array points, where points[i] = [xi, yi] represents the coordinates of the ith point on the Cartesian plane. The Manhattan distance between two points points[i] = [xi, yi] and points[j] = [xj, yj] is |xi - xj| + |yi - yj|. Split the n points into exactly two non-empty groups. The partition factor of a split is the minimum Manhattan distance among all unordered pairs of points that lie in the same group. Return the maximum possible partition factor over all valid splits. Note: A group of size 1 contributes no intra-group pairs. When n = 2 (both groups size 1), there are no intra-group pairs, so define the partition factor as 0.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_partition_factor(points: Vec<Vec<i32>>) -> i32 {
    let n = points.len();
    if n == 2 {
      return 0;
    }
    // Compute all pairwise distances
    let mut dists: Vec<(i32, usize, usize)> = Vec::new();
    for i in 0..n {
      for j in i + 1..n {
        let d = (points[i][0] - points[j][0]).abs() + (points[i][1] - points[j][1]).abs();
        dists.push((d, i, j));
      }
    }
    dists.sort();
    // Binary search: can we achieve partition factor >= X?
    // That means: we can 2-color points such that all pairs with dist < X are in different groups.
    // So edges with dist < X force the two endpoints to be in different groups (different colors).
    // This is satisfiable iff the "conflict graph" of edges with dist < X is bipartite.
    // Additionally, we need both colors to be non-empty.
    let unique_dists: Vec<i32> = {
      let mut v: Vec<i32> = dists.iter().map(|&(d, _, _)| d).collect();
      v.dedup();
      v
    };
    // check(threshold): can we 2-color all points so every pair with dist < threshold
    // is in different groups (i.e., the "conflict graph" for dist < threshold is bipartite)?
    // Monotone: check(d) => check(d') for d' <= d, so binary search for maximum.
    let check = |threshold: i32| -> bool {
      let mut adj = vec![vec![]; n];
      for &(d, u, v) in &dists {
        if d < threshold {
          adj[u].push(v);
          adj[v].push(u);
        } else {
          break; // dists is sorted
        }
      }
      let mut color = vec![-1i32; n];
      let mut num_components = 0usize;
      for start in 0..n {
        if color[start] != -1 { continue; }
        num_components += 1;
        color[start] = 0;
        let mut queue = std::collections::VecDeque::new();
        queue.push_back(start);
        while let Some(u) = queue.pop_front() {
          for &v in &adj[u] {
            if color[v] == -1 {
              color[v] = 1 - color[u];
              queue.push_back(v);
            } else if color[v] == color[u] {
              return false; // odd cycle: not bipartite
            }
          }
        }
      }
      // With >= 2 components we can freely assign each to a group → both non-empty.
      if num_components >= 2 { return true; }
      // Single connected component: both colors appear iff there is at least one edge.
      let c0 = color.iter().filter(|&&c| c == 0).count();
      c0 > 0 && c0 < n
    };
    // Binary search: find maximum d in unique_dists where check(d) is true.
    // O(n^2 log n) instead of O(n^4).
    let mut lo = 0usize;
    let mut hi = unique_dists.len();
    while lo < hi {
      let mid = (lo + hi + 1) / 2;
      if check(unique_dists[mid - 1]) {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    if lo == 0 { 0 } else { unique_dists[lo - 1] }
  }
}