Perfect Rectangle

hard math geometry hash set

Problem

Given a set of axis-aligned rectangles [x1,y1,x2,y2], return whether their union forms a perfect, exact rectangle.

Inputrects = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]

Outputtrue

Areas sum to bounding-box area; four extreme corners appear exactly once each.

rects (x1,y1,x2,y2 ;)

def is_rectangle_cover(rects):
    area = 0
    corners = set()
    X1 = Y1 = float("inf"); X2 = Y2 = float("-inf")
    for x1, y1, x2, y2 in rects:
        area += (x2 - x1) * (y2 - y1)
        X1, Y1 = min(X1, x1), min(Y1, y1)
        X2, Y2 = max(X2, x2), max(Y2, y2)
        for p in [(x1, y1), (x1, y2), (x2, y1), (x2, y2)]:
            corners ^= {p}  # symmetric diff toggles
    if area != (X2 - X1) * (Y2 - Y1): return False
    return corners == {(X1, Y1), (X1, Y2), (X2, Y1), (X2, Y2)}

function isRectangleCover(rects) {
  let area = 0;
  let X1 = Infinity, Y1 = Infinity, X2 = -Infinity, Y2 = -Infinity;
  const corners = new Set();
  for (const [x1, y1, x2, y2] of rects) {
    area += (x2 - x1) * (y2 - y1);
    X1 = Math.min(X1, x1); Y1 = Math.min(Y1, y1);
    X2 = Math.max(X2, x2); Y2 = Math.max(Y2, y2);
    for (const p of [`${x1},${y1}`, `${x1},${y2}`, `${x2},${y1}`, `${x2},${y2}`]) {
      if (corners.has(p)) corners.delete(p); else corners.add(p);
    }
  }
  if (area !== (X2 - X1) * (Y2 - Y1)) return false;
  return corners.size === 4 &&
    corners.has(`${X1},${Y1}`) && corners.has(`${X1},${Y2}`) &&
    corners.has(`${X2},${Y1}`) && corners.has(`${X2},${Y2}`);
}

class Solution {
    public boolean isRectangleCover(int[][] rects) {
        long area = 0; int X1 = Integer.MAX_VALUE, Y1 = Integer.MAX_VALUE, X2 = Integer.MIN_VALUE, Y2 = Integer.MIN_VALUE;
        Set corners = new HashSet<>();
        for (int[] r : rects) {
            area += (long)(r[2] - r[0]) * (r[3] - r[1]);
            X1 = Math.min(X1, r[0]); Y1 = Math.min(Y1, r[1]);
            X2 = Math.max(X2, r[2]); Y2 = Math.max(Y2, r[3]);
            String[] ps = { r[0]+","+r[1], r[0]+","+r[3], r[2]+","+r[1], r[2]+","+r[3] };
            for (String p : ps) if (!corners.add(p)) corners.remove(p);
        }
        if (area != (long)(X2 - X1) * (Y2 - Y1)) return false;
        return corners.size() == 4 &&
            corners.contains(X1+","+Y1) && corners.contains(X1+","+Y2) &&
            corners.contains(X2+","+Y1) && corners.contains(X2+","+Y2);
    }
}

bool isRectangleCover(vector>& rects) {
    long long area = 0;
    int X1 = INT_MAX, Y1 = INT_MAX, X2 = INT_MIN, Y2 = INT_MIN;
    unordered_set corners;
    for (auto& r : rects) {
        area += (long long)(r[2] - r[0]) * (r[3] - r[1]);
        X1 = min(X1, r[0]); Y1 = min(Y1, r[1]);
        X2 = max(X2, r[2]); Y2 = max(Y2, r[3]);
        string ps[4] = { to_string(r[0])+","+to_string(r[1]), to_string(r[0])+","+to_string(r[3]), to_string(r[2])+","+to_string(r[1]), to_string(r[2])+","+to_string(r[3]) };
        for (auto& p : ps) if (!corners.insert(p).second) corners.erase(p);
    }
    if (area != (long long)(X2 - X1) * (Y2 - Y1)) return false;
    return corners.size() == 4 &&
        corners.count(to_string(X1)+","+to_string(Y1)) && corners.count(to_string(X1)+","+to_string(Y2)) &&
        corners.count(to_string(X2)+","+to_string(Y1)) && corners.count(to_string(X2)+","+to_string(Y2));
}

Explanation

The union of many small rectangles forms one perfect big rectangle only if two things hold at once: the areas add up exactly, and the corners line up cleanly. We check both with a single pass.

First, the area check: sum the area of every sub-rectangle and compare it to the area of the overall bounding box (from the smallest x1,y1 to the largest x2,y2). If they differ, there is either a gap or an overlap, so it cannot be perfect.

Second, the corner check: track every rectangle's four corners in a set, toggling each one in and out (the ^= / add-or-delete trick). An interior corner is shared by an even number of rectangles and cancels out; only corners appearing an odd number of times survive. For a perfect cover, exactly the four bounding-box corners should remain.

Example: the input [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]] tiles the box from (1,1) to (4,4). The areas sum to the box area 9, and after toggling, only the four extreme corners (1,1),(1,4),(4,1),(4,4) are left, so it returns true.

We touch each rectangle once and do constant work per corner, so the time is linear with linear extra space for the corner set.

Time: O(n) Space: O(n)