Rectangle Area
Medium · Geometry · Math · Geometry
Problem
Two rectangles lie on a plane with their sides parallel to the axes. Rectangle A has bottom-left corner (ax1, ay1) and top-right corner (ax2, ay2); rectangle B has bottom-left corner (bx1, by1) and top-right corner (bx2, by2).
Return the total area covered by the two rectangles. Where they overlap, that area counts only once.
A rectangle may be flat (zero width or zero height), in which case its area is 0.
Examples
Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2 Output: 45
A is 6 × 4 = 24 and B is 9 × 3 = 27. They share x from 0 to 3 and y from 0 to 2, an area of 6, which was counted twice: 24 + 27 − 6 = 45.
Input: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2 Output: 16
Both are the same 4 × 4 square, so the overlap is all of it: 16 + 16 − 16 = 16.
Input: ax1 = 0, ay1 = 0, ax2 = 2, ay2 = 2, bx1 = 3, by1 = 0, bx2 = 5, by2 = 2 Output: 8
On the x-axis the overlap length is min(2, 5) - max(0, 3) = -1, clamped to 0. Nothing is shared: 4 + 4 = 8.
Constraints
- -10^4 <= ax1 <= ax2 <= 10^4
- -10^4 <= ay1 <= ay2 <= 10^4
- -10^4 <= bx1 <= bx2 <= 10^4
- -10^4 <= by1 <= by2 <= 10^4
Approaches
- Baseline: count unit squares — time O(W · H) for the bounding box, space O(1)
Follow-up
What if there are n rectangles? Adding every area and subtracting every pairwise overlap is no longer enough, because three rectangles can share a region (inclusion–exclusion needs 2^n terms). Cut the plane at every distinct x-coordinate and, in each vertical strip, add up the merged lengths of the y-intervals of the rectangles that span it, as in the "Area covered by many rectangles" use case.
Related problems
Start free on Cariara · Coding problems · System design studio
