DSA problem
Perfect Rectangle
Given an array of axis-aligned rectangles rectangles where rectangles[i] = [x_i, y_i, a_i, b_i] denotes the rectangle with bottom-left corner (x_i, y_i) and top-right corner (a_i, b_i), return true if and only if every point in the union of the rectangles is also in some axis-aligned rectangle covered exactly once, with no gaps or overlaps — i.e. the union is itself a single axis-aligned rectangle.
Two simple invariants together imply a perfect cover. (a) Area: the sum of the areas of all input rectangles equals the area of the bounding rectangle formed by the global min-x, min-y, max-x, max-y. If the sum is greater there must be overlap; if smaller there must be a gap. (b) Corner parity: each of the four corners of the bounding rectangle appears as a corner of exactly one input rectangle, and every other corner appears an even number of times. Internally, corners that "match up" pair off in groups of 2 or 4; an unmatched interior corner means a gap or overlap.
The optimal implementation walks the rectangle list once, accumulating the area sum and tracking the four global extremes. Simultaneously it maintains a hash set of corner strings (e.g. "x,y"); for each of the four corners of each rectangle, toggle membership (insert if absent, remove if present). When the loop ends, the set must contain exactly the four bounding-rectangle corners.
This gives O(n) average time (assuming hash operations are O(1)) and O(n) space. The approach is elegantly simple compared to running a full vertical sweep with a segment tree: it does not even need to sort the input, and the only arithmetic is integer corner coordinates which fit comfortably in 64-bit (or BigInt where applicable).
Examples
rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]truerectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]falserectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[3,2,4,4]]falseConstraints
- 1 <= rectangles.length <= 2 * 10^4
- rectangles[i].length == 4
- -10^5 <= rectangles[i][j] <= 10^5
- rectangles[i][0] < rectangles[i][2] and rectangles[i][1] < rectangles[i][3]
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.