Minimum area rectangle ii

Array Hash Table Math Geometry

55.9% acceptance

Feb 25, 2026

411

486

You are given an array of points in the X-Y plane points where points[i] = [xi, yi]. Return the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the X and Y axes. If there is not any such rectangle, return 0. Answers within 10-5 of the actual answer will be accepted.

Solution

Rust

Time O(n³)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_area_free_rect(points: Vec<Vec<i32>>) -> f64 {
    use std::collections::HashSet;
    let set: HashSet<(i32,i32)> = points.iter().map(|p| (p[0], p[1])).collect();
    let n = points.len();
    let mut min_area = f64::MAX;
    for i in 0..n {
      for j in i+1..n {
        for k in j+1..n {
          // Check if (i,j,k) form a right angle at j or k or i
          let (ax, ay) = (points[i][0], points[i][1]);
          let (bx, by) = (points[j][0], points[j][1]);
          let (cx, cy) = (points[k][0], points[k][1]);
          // Try each as the right angle vertex
          for &(ox, oy, p1x, p1y, p2x, p2y) in &[(ax,ay,bx,by,cx,cy),(bx,by,ax,ay,cx,cy),(cx,cy,ax,ay,bx,by)] {
            let (v1x, v1y) = (p1x-ox, p1y-oy);
            let (v2x, v2y) = (p2x-ox, p2y-oy);
            if v1x*v2x + v1y*v2y == 0 {
              // Right angle at O. Fourth point = p1 + p2 - O
              let (dx, dy) = (p1x+p2x-ox, p1y+p2y-oy);
              if set.contains(&(dx, dy)) {
                let area = (((v1x*v1x + v1y*v1y) as f64) * ((v2x*v2x + v2y*v2y) as f64)).sqrt();
                min_area = min_area.min(area);
              }
            }
          }
        }
      }
    }
    if min_area == f64::MAX { 0.0 } else { min_area }
  }
}