LeetCode 223: Rectangle Area

Problem Restatement

We are given two axis-aligned rectangles in a 2D plane.

The first rectangle is defined by:

(ax1, ay1)
(ax2, ay2)

The second rectangle is defined by:

(bx1, by1)
(bx2, by2)

Each pair represents the bottom-left corner and top-right corner of a rectangle.

We need to return the total area covered by both rectangles. If the rectangles overlap, the overlapping region should be counted only once. The official statement gives the same coordinate definition and asks for the total area covered by the two rectangles.

Input and Output

Example function shape:

def computeArea(
    ax1: int,
    ay1: int,
    ax2: int,
    ay2: int,
    bx1: int,
    by1: int,
    bx2: int,
    by2: int,
) -> int:
    ...

Examples

Example 1:

ax1 = -3
ay1 = 0
ax2 = 3
ay2 = 4

bx1 = 0
by1 = -1
bx2 = 9
by2 = 2

Area of rectangle A:

(3 - (-3)) * (4 - 0) = 6 * 4 = 24

Area of rectangle B:

(9 - 0) * (2 - (-1)) = 9 * 3 = 27

They overlap in a rectangle of width 3 and height 2.

Overlap area:

3 * 2 = 6

Total covered area:

24 + 27 - 6 = 45

Answer:

45

Example 2:

ax1 = -2
ay1 = -2
ax2 = 2
ay2 = 2

bx1 = -2
by1 = -2
bx2 = 2
by2 = 2

The rectangles are identical.

Each area is:

4 * 4 = 16

The overlap is also 16.

Total:

16 + 16 - 16 = 16

Answer:

16

First Thought

If the rectangles do not overlap, the answer is easy:

area A + area B

But if they overlap, that formula counts the overlap twice.

So the correct formula is:

area A + area B - overlap area

The entire problem is reduced to computing the overlap area.

Rectangle Area Formula

For a rectangle with bottom-left corner (x1, y1) and top-right corner (x2, y2):

width = x2 - x1
height = y2 - y1
area = width * height

So:

area_a = (ax2 - ax1) * (ay2 - ay1)
area_b = (bx2 - bx1) * (by2 - by1)

Key Insight: Find the Intersection Rectangle

If two axis-aligned rectangles overlap, their intersection is also an axis-aligned rectangle.

The overlap’s left edge is the larger of the two left edges:

overlap_left = max(ax1, bx1)

The overlap’s right edge is the smaller of the two right edges:

overlap_right = min(ax2, bx2)

So the overlap width is:

overlap_width = overlap_right - overlap_left

Similarly for the y-axis:

overlap_bottom = max(ay1, by1)
overlap_top = min(ay2, by2)
overlap_height = overlap_top - overlap_bottom

If either dimension is negative or zero, the rectangles do not overlap with positive area.

So we clamp each dimension at zero:

overlap_width = max(0, overlap_width)
overlap_height = max(0, overlap_height)

Algorithm

1. Compute the area of the first rectangle.
2. Compute the area of the second rectangle.
3. Compute the overlap width.
4. Compute the overlap height.
5. Compute overlap area.
6. Return:

area_a + area_b - overlap_area

Walkthrough

Use:

A = [-3, 0, 3, 4]
B = [0, -1, 9, 2]

Rectangle A:

width = 3 - (-3) = 6
height = 4 - 0 = 4
area = 24

Rectangle B:

width = 9 - 0 = 9
height = 2 - (-1) = 3
area = 27

Overlap x-range:

left = max(-3, 0) = 0
right = min(3, 9) = 3
width = 3 - 0 = 3

Overlap y-range:

bottom = max(0, -1) = 0
top = min(4, 2) = 2
height = 2 - 0 = 2

Overlap area:

3 * 2 = 6

Final answer:

24 + 27 - 6 = 45

Touching Edges

If two rectangles only touch at an edge, the overlap area is zero.

Example:

A = [0, 0, 2, 2]
B = [2, 0, 4, 2]

Overlap width:

min(2, 4) - max(0, 2) = 2 - 2 = 0

The rectangles touch, but do not overlap with positive area.

So we subtract 0.

Correctness

The area of both rectangles added together counts every point covered by rectangle A and every point covered by rectangle B.

If the rectangles do not overlap, this sum is already correct.

If the rectangles overlap, every point inside the intersection region is counted twice: once from A and once from B. To count covered area only once, we must subtract the intersection area exactly once.

The algorithm computes the intersection rectangle by taking the rightmost left edge, the leftmost right edge, the higher bottom edge, and the lower top edge. These are exactly the boundaries shared by both rectangles.

If the computed width or height is not positive, the rectangles have no positive-area overlap, so the overlap area is 0.

Therefore the returned value:

area_a + area_b - overlap_area

is exactly the total area covered by the two rectangles.

Complexity

Implementation

class Solution:
    def computeArea(
        self,
        ax1: int,
        ay1: int,
        ax2: int,
        ay2: int,
        bx1: int,
        by1: int,
        bx2: int,
        by2: int,
    ) -> int:
        area_a = (ax2 - ax1) * (ay2 - ay1)
        area_b = (bx2 - bx1) * (by2 - by1)

        overlap_width = min(ax2, bx2) - max(ax1, bx1)
        overlap_height = min(ay2, by2) - max(ay1, by1)

        overlap_width = max(0, overlap_width)
        overlap_height = max(0, overlap_height)

        overlap_area = overlap_width * overlap_height

        return area_a + area_b - overlap_area

Code Explanation

Compute the first rectangle’s area:

area_a = (ax2 - ax1) * (ay2 - ay1)

Compute the second rectangle’s area:

area_b = (bx2 - bx1) * (by2 - by1)

Compute possible overlap width:

overlap_width = min(ax2, bx2) - max(ax1, bx1)

Compute possible overlap height:

overlap_height = min(ay2, by2) - max(ay1, by1)

Clamp negative values to zero:

overlap_width = max(0, overlap_width)
overlap_height = max(0, overlap_height)

Compute overlap area:

overlap_area = overlap_width * overlap_height

Subtract the overlap once:

return area_a + area_b - overlap_area

Alternative: Explicit No-Overlap Check

We can first check whether the rectangles do not overlap.

There is no overlap if one rectangle is completely left, right, above, or below the other.

class Solution:
    def computeArea(
        self,
        ax1: int,
        ay1: int,
        ax2: int,
        ay2: int,
        bx1: int,
        by1: int,
        bx2: int,
        by2: int,
    ) -> int:
        area_a = (ax2 - ax1) * (ay2 - ay1)
        area_b = (bx2 - bx1) * (by2 - by1)

        no_overlap = (
            ax2 <= bx1 or
            bx2 <= ax1 or
            ay2 <= by1 or
            by2 <= ay1
        )

        if no_overlap:
            return area_a + area_b

        overlap_width = min(ax2, bx2) - max(ax1, bx1)
        overlap_height = min(ay2, by2) - max(ay1, by1)

        return area_a + area_b - overlap_width * overlap_height

The clamping version is shorter and avoids separate case handling.

Testing

def run_tests():
    s = Solution()

    assert s.computeArea(-3, 0, 3, 4, 0, -1, 9, 2) == 45
    assert s.computeArea(-2, -2, 2, 2, -2, -2, 2, 2) == 16
    assert s.computeArea(0, 0, 2, 2, 2, 0, 4, 2) == 8
    assert s.computeArea(0, 0, 2, 2, 3, 3, 5, 5) == 8
    assert s.computeArea(0, 0, 4, 4, 1, 1, 2, 2) == 16
    assert s.computeArea(0, 0, 4, 4, 2, 2, 6, 6) == 28

    print("all tests passed")

run_tests()