Perfect Rectangle

Perfect Rectangle

What is this problem about?

The Perfect Rectangle problem gives you a list of non-overlapping rectangles and asks whether they exactly tile a larger rectangle with no gaps or overlaps. This hard coding problem uses geometric properties: the union area must equal the bounding rectangle area, and all interior corner points must cancel out (appear an even number of times). The array, math, hash table, line sweep, and geometry interview pattern is tested.

Why is this asked in interviews?

Meta and Google ask this because it tests both geometric reasoning and careful case analysis. The corner point cancellation method is elegant: valid tiling requires that all interior corners appear 2 or 4 times, while only the 4 outer corners appear exactly once.

Algorithmic pattern used

Area check + corner counting. Compute: (1) total area of all rectangles, (2) bounding rectangle area (from min/max coordinates), (3) count of corner occurrences using a set. A valid tiling satisfies: total area = bounding area, and only the 4 bounding corners appear an odd number of times (all others appear even times). Use XOR-in/XOR-out with corner sets.

Example explanation

Rectangles: [(0,0,1,1),(1,0,2,1),(0,1,2,2)]. Total area = 1+1+2 = 4. Bounding: (0,0)→(2,2), area=4. ✓ Corners: (0,0)→odd times, (2,0)→odd, (0,2)→odd, (2,2)→odd. Only 4 corners appear odd times. Return true.

Common mistakes candidates make

• Only checking total area without corner verification (doesn't catch overlapping arrangements with same total area).
• Using a frequency map when XOR-based set toggling is cleaner.
• Not handling the bounding rectangle coordinates correctly (must find min/max of all coordinates).
• Off-by-one in rectangle corner coordinates.

Interview preparation tip

Perfect tiling problems combine area checking with combinatorial corner counting. The dual condition — correct area AND correct corner parity — is necessary and sufficient. Practice this on "valid partition of L-shaped regions" and similar geometric tiling problems. The set-toggle (add if absent, remove if present) technique for counting even/odd occurrences is a widely reusable pattern.