Perfect rectangle

Array Hash Table Math Geometry Sweep Line

37.3% acceptance

Jan 12, 2026

952

120

Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi). Return true if all the rectangles together form an exact cover of a rectangular region.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_rectangle_cover(rectangles: Vec<Vec<i32>>) -> bool {
    let mut area = 0;
    let mut corners = std::collections::HashSet::new();
    let (mut min_x, mut min_y, mut max_x, mut max_y) = (i32::MAX, i32::MAX, i32::MIN, i32::MIN);
    
    for rect in rectangles.iter() {
      let (x1, y1, x2, y2) = (rect[0], rect[1], rect[2], rect[3]);
      
      min_x = min_x.min(x1);
      min_y = min_y.min(y1);
      max_x = max_x.max(x2);
      max_y = max_y.max(y2);
      
      area += (x2 - x1) * (y2 - y1);
      
      let points = [(x1, y1), (x1, y2), (x2, y1), (x2, y2)];
      for &p in &points {
        if corners.contains(&p) {
          corners.remove(&p);
        } else {
          corners.insert(p);
        }
      }
    }
    
    let expected_area = (max_x - min_x) * (max_y - min_y);
    let expected_corners = std::collections::HashSet::from([(min_x, min_y), (min_x, max_y), (max_x, min_y), (max_x, max_y)]);
    
    area == expected_area && corners == expected_corners
  }
}