Rectangle Area

Total = sum of areas minus the overlap area; overlap dims are max(0, min - max) on each axis.

Medium
Time O(1) Space O(1)
LeetCode
3 min read
geometry math

Problem#

Given two axis-aligned rectangles by their bottom-left and top-right corners, return their combined covered area (union).

Examples#

  • (-3,0,3,4), (0,-1,9,2)45.
  • (-2,-2,2,2), (-2,-2,2,2)16.

Constraints#

  • Coordinates fit in 32-bit signed int.

Approach#

area(A) + area(B) - area(A ∩ B). Overlap width = max(0, min(rightA, rightB) - max(leftA, leftB)), similarly for height.

Solution#

Rectangle Area
class Solution {
public:
int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
long long a = (long long)(ax2 - ax1) * (ay2 - ay1);
long long b = (long long)(bx2 - bx1) * (by2 - by1);
long long ow = max(0, min(ax2, bx2) - max(ax1, bx1));
long long oh = max(0, min(ay2, by2) - max(ay1, by1));
return (int)(a + b - ow * oh);
}
};

Editorial#

Inclusion-exclusion in two dimensions. The max(0, ...) guards the case where the rectangles don’t overlap (negative overlap width). long long casts prevent overflow when both areas approach (2 * 10^4)^2.

Complexity#

  • Time: O(1).
  • Space: O(1).

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.