Find the number of ways to place people i

Array Math Geometry Sorting Enumeration

64.0% acceptance

Feb 25, 2026

482

180

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]. Count the number of pairs of points (A, B), where A is on the upper left side of B, and there are no other points in the rectangle (or line) they make (including the border), except for the points A and B. Return the count.

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
  }
}