Maximum area rectangle with point constraints i

Array Math Binary Indexed Tree Segment Tree Geometry Sorting Enumeration

51.3% acceptance

Feb 24, 2026

You are given an array points where points[i] = [xi, yi] represents the coordinates of a point on an infinite plane. Your task is to find the maximum area of a rectangle that: Can be formed using four of these points as its corners. Does not contain any other point inside or on its border. Has its edges parallel to the axes. Return the maximum area that you can obtain or -1 if no such rectangle is possible.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_rectangle_area(points: Vec<Vec<i32>>) -> i32 {
    let n = points.len();
    let point_set: std::collections::HashSet<(i32,i32)> = points.iter()
      .map(|p| (p[0], p[1])).collect();
    
    let mut ans = -1i32;
    
    // Try all pairs as potential top-right and bottom-left corners
    for i in 0..n {
      for j in 0..n {
        if i == j { continue; }
        let (x1, y1) = (points[i][0], points[i][1]);
        let (x2, y2) = (points[j][0], points[j][1]);
        if x1 >= x2 || y1 >= y2 { continue; } // ensure valid rectangle (x1<x2, y1<y2)
        // Check all 4 corners exist
        if !point_set.contains(&(x1, y2)) || !point_set.contains(&(x2, y1)) {
          continue;
        }
        // Check no other point is strictly inside or on border
        let valid = points.iter().all(|p| {
          let (px, py) = (p[0], p[1]);
          // Allow corners
          if (px == x1 || px == x2) && (py == y1 || py == y2) { return true; }
          // Any other point inside or on border?
          if px >= x1 && px <= x2 && py >= y1 && py <= y2 { return false; }
          true
        });
        if valid {
          ans = ans.max((x2 - x1) * (y2 - y1));
        }
      }
    }
    ans
  }
}