Find the number of ways to place people ii

Array Math Geometry Sorting Enumeration

64.4% acceptance

Feb 25, 2026

357

You are given a 2D array points of size n x 2 representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi]. You have to place n people, including Alice and Bob, at these points such that there is exactly one person at every point. Alice wants to be alone with Bob, so Alice will build a rectangular fence with Alice's position as the upper left corner and Bob's position as the lower right corner of the fence. Return the number of pairs of points where you can place Alice and Bob, such that Alice does not become sad on building the fence.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_pairs(mut points: Vec<Vec<i32>>) -> i32 {
    points.sort_by(|a, b| a[0].cmp(&b[0]).then(b[1].cmp(&a[1])));
    let n = points.len();
    let mut ans = 0;
    for i in 0..n {
      let mut max_y = i32::MIN;
      for j in (i+1)..n {
        if points[j][1] <= points[i][1] && points[j][1] > max_y {
          ans += 1;
        }
        if points[j][1] <= points[i][1] {
          max_y = max_y.max(points[j][1]);
        }
      }
    }
    ans
  }
}