Hard

Quiz

#391 Perfect Rectangle

APPROACH

You are given an array rectangles where rectangles[i] = [xi, yi, ai, bi] describes an axis-aligned rectangle with bottom-left corner (xi, yi) and top-right corner (ai, bi).

Return true if and only if the union of all these rectangles forms a single larger rectangle with no overlapping regions and no uncovered gaps.

Example 1:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]

Output: true

Explanation: All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

Input: rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]

Output: false

Explanation: Because there is a gap between the two rectangular regions.

Example 3:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]

Output: false

Explanation: Because two of the rectangles overlap with each other.

1 of 4

1:00

What is the optimal approach for this problem?