Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardsweep-line

Perfect Rectangle

Problem (restated)

Axis-aligned rectangles [x1, y1, x2, y2]. Return whether they tile a single larger rectangle exactly: no gaps, no overlaps.

Intuition

Two invariants replace a full 2D sweep. (1) Total area equals the bounding box. (2) Every interior corner is shared an even number of times (toggle in a set → disappears); the four extreme corners remain once. Overlap or a hole breaks one of those.

Approaches

Area + corner parity

Unverified

Time O(n)Space O(n)

Idea. Accumulate area and bounding box. Toggle each of the four corners in a set. Accept iff area == bbox and the set is exactly the four bbox corners.

Walkthrough. Four rectangles that fill [1,1]–[4,4] leave only those four points. An overlap inflates area; a gap leaves extra interior corners.

Trade-offs. O(n), no sort. A literal sweep (active y-intervals per x-event) also works and matches the template more literally, at O(n log n). Area overflow: use 64-bit.

Solution

export function isRectangleCover(rectangles: number[][]): boolean {
  let area = 0;
  let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
  const corners = new Set<string>();
  const toggle = (x: number, y: number) => {
    const k = `${x},${y}`;
    if (corners.has(k)) corners.delete(k);
    else corners.add(k);
  };
  for (const r of rectangles) {
    const x1 = r[0]!, y1 = r[1]!, x2 = r[2]!, y2 = r[3]!;
    area += (x2 - x1) * (y2 - y1);
    minX = Math.min(minX, x1); minY = Math.min(minY, y1);
    maxX = Math.max(maxX, x2); maxY = Math.max(maxY, y2);
    toggle(x1, y1); toggle(x1, y2); toggle(x2, y1); toggle(x2, y2);
  }
  if (area !== (maxX - minX) * (maxY - minY)) return false;
  if (corners.size !== 4) return false;
  return (
    corners.has(`${minX},${minY}`) &&
    corners.has(`${minX},${maxY}`) &&
    corners.has(`${maxX},${minY}`) &&
    corners.has(`${maxX},${maxY}`)
  );
}

export function isRectangleCover(rectangles: number[][]): boolean {
  let area = 0;
  let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
  const corners = new Set<string>();
  const toggle = (x: number, y: number) => {
    const k = `${x},${y}`;
    if (corners.has(k)) corners.delete(k);
    else corners.add(k);
  };
  for (const r of rectangles) {
    const x1 = r[0]!, y1 = r[1]!, x2 = r[2]!, y2 = r[3]!;
    area += (x2 - x1) * (y2 - y1);
    minX = Math.min(minX, x1); minY = Math.min(minY, y1);
    maxX = Math.max(maxX, x2); maxY = Math.max(maxY, y2);
    toggle(x1, y1); toggle(x1, y2); toggle(x2, y1); toggle(x2, y2);
  }
  if (area !== (maxX - minX) * (maxY - minY)) return false;
  if (corners.size !== 4) return false;
  return (
    corners.has(`${minX},${minY}`) &&
    corners.has(`${minX},${maxY}`) &&
    corners.has(`${maxX},${minY}`) &&
    corners.has(`${maxX},${maxY}`)
  );
}

Template connection

Perfect-rectangle shape of Sweep Line: the area check plus even-odd corner count is the discrete form of “coverage is exactly 1 everywhere.” LC 218 tracks max height; this tracks exact cover.

Reflection

The summed area must equal the bounding box, and each corner toggles in a set. At the end the set must be exactly the four outer corners.
Area alone misses a hole. Corners alone miss extra overlapping area.
One rectangle is true. Two overlapping pieces are false. An interior corner appears an even number of times and leaves the set.