LeetCode 223 - Rectangle Area

Difficulty: 🟡 Medium
Topics: Math, Geometry

Solution

Problem Understanding

The problem gives the coordinates of two axis-aligned rectangles on a 2D plane. Each rectangle is represented using two corner points:

Bottom-left corner (x1, y1)
Top-right corner (x2, y2)

For the first rectangle, the coordinates are:

(ax1, ay1) for the bottom-left
(ax2, ay2) for the top-right

For the second rectangle, the coordinates are:

(bx1, by1) for the bottom-left
(bx2, by2) for the top-right

The task is to compute the total area covered by both rectangles combined.

At first glance, it may seem sufficient to calculate the area of each rectangle independently and add them together. However, the rectangles may overlap. If they do, the overlapping region would be counted twice. To obtain the correct total covered area, we must subtract the overlapping area once.

The rectangles are rectilinear, meaning their sides are parallel to the x-axis and y-axis. This property makes overlap computation straightforward because overlap can be computed independently along the x-axis and y-axis.

The coordinate constraints range from -10^4 to 10^4. These are relatively small values, but the important observation is that the input size is constant. We only ever process two rectangles, so efficiency is not about scaling with input size but about choosing the correct geometric computation.

Several edge cases are important:

The rectangles may not overlap at all
One rectangle may be completely inside the other
The rectangles may only touch at an edge or corner
The rectangles may be identical
Coordinates may be negative

A naive implementation can easily produce negative overlap widths or heights when rectangles do not intersect. Proper handling requires clamping overlap dimensions to zero.

Approaches

Brute Force Approach

A brute force geometric approach would be to treat the plane as a grid and count every unit square covered by at least one rectangle.

For every integer coordinate inside the bounding region, we could determine whether that point lies inside rectangle A, rectangle B, or both. By counting all covered unit cells, we would obtain the total area.

This approach is conceptually correct because it directly measures covered space. However, it is computationally expensive. The coordinate range spans up to 20,000 units in each dimension, so iterating over the entire plane would require hundreds of millions of operations in the worst case.

Even though the constraints are not extremely large, this approach is unnecessary because geometry provides a direct formula.

Optimal Geometric Approach

The key insight is that the total covered area can be computed using the inclusion-exclusion principle.

The formula is:

$$\text{Total Area} = \text{Area of A} + \text{Area of B} - \text{Overlap Area}$$

The only challenging part is computing the overlap area correctly.

Two rectangles overlap if their projections overlap on both axes.

The overlap width is:

$$\min(ax2, bx2) - \max(ax1, bx1)$$

The overlap height is:

$$\min(ay2, by2) - \max(ay1, by1)$$

If either value is negative, the rectangles do not overlap along that dimension, so the overlap area becomes zero.

This approach is efficient because it performs only a constant number of arithmetic operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(W × H)	O(1)	Iterates over the plane and counts covered cells
Optimal	O(1)	O(1)	Uses rectangle area formulas and overlap computation

Algorithm Walkthrough

Compute the area of the first rectangle.

The width is ax2 - ax1, and the height is ay2 - ay1.

The area is:

$$(ax2 - ax1) \times (ay2 - ay1)$$ 2. Compute the area of the second rectangle.

Similarly:

$$(bx2 - bx1) \times (by2 - by1)$$ 3. Compute the overlap width.

The left boundary of the overlap region is the larger left edge:

$$\max(ax1, bx1)$$

The right boundary is the smaller right edge:

$$\min(ax2, bx2)$$

Therefore:

$$\text{overlapWidth} = \min(ax2, bx2) - \max(ax1, bx1)$$ 4. Compute the overlap height.

Similarly:

$$\text{overlapHeight} = \min(ay2, by2) - \max(ay1, by1)$$ 5. Prevent negative overlap dimensions.

If rectangles do not overlap, one or both overlap dimensions become negative.

Since negative area is meaningless, clamp them to zero:

$$\text{overlapWidth} = \max(0, \text{overlapWidth})$$

$$\text{overlapHeight} = \max(0, \text{overlapHeight})$$ 6. Compute the overlap area.

$$\text{overlapArea} = \text{overlapWidth} \times \text{overlapHeight}$$ 7. Apply inclusion-exclusion.

Add both rectangle areas and subtract the duplicated overlap:

$$\text{result} = \text{areaA} + \text{areaB} - \text{overlapArea}$$

Why it works

Each rectangle area contributes all of its covered space. If the rectangles overlap, the overlapping region is counted twice, once in each rectangle's area. Subtracting the overlap area once removes this duplication and leaves exactly the union area of the two rectangles.

The overlap computation works because two axis-aligned rectangles intersect precisely when their intervals overlap on both axes.

Python Solution

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

        # Area of rectangle A
        area_a = (ax2 - ax1) * (ay2 - ay1)

        # Area of rectangle B
        area_b = (bx2 - bx1) * (by2 - by1)

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

        # Clamp negative overlaps to zero
        overlap_width = max(0, overlap_width)
        overlap_height = max(0, overlap_height)

        # Overlapping area
        overlap_area = overlap_width * overlap_height

        # Total covered area
        return area_a + area_b - overlap_area

The implementation directly follows the geometric formula developed earlier.

The first section computes the individual rectangle areas using width multiplied by height.

The next section computes overlap dimensions independently for the x-axis and y-axis. Using min for the right or top boundaries and max for the left or bottom boundaries isolates the intersecting interval.

The clamping step is critical. Without it, non-overlapping rectangles would produce negative overlap dimensions, leading to incorrect negative overlap areas.

Finally, the inclusion-exclusion formula combines the results into the final answer.

Go Solution

func computeArea(ax1 int, ay1 int, ax2 int, ay2 int, bx1 int, by1 int, bx2 int, by2 int) int {
    // Area of rectangle A
    areaA := (ax2 - ax1) * (ay2 - ay1)

    // Area of rectangle B
    areaB := (bx2 - bx1) * (by2 - by1)

    // Compute overlap dimensions
    overlapWidth := min(ax2, bx2) - max(ax1, bx1)
    overlapHeight := min(ay2, by2) - max(ay1, by1)

    // Clamp negative overlaps to zero
    overlapWidth = max(0, overlapWidth)
    overlapHeight = max(0, overlapHeight)

    // Overlap area
    overlapArea := overlapWidth * overlapHeight

    // Total covered area
    return areaA + areaB - overlapArea
}

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go implementation mirrors the Python solution closely. Since Go does not provide built-in integer min and max functions for primitive integers, helper functions are implemented manually.

Integer overflow is not a concern here because coordinate ranges are small enough that all intermediate area computations safely fit within Go's int type.

Worked Examples

Example 1

Input:

ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4
bx1 = 0, by1 = -1, bx2 = 9, by2 = 2

Step 1: Compute rectangle areas

Rectangle	Width	Height	Area
A	3 - (-3) = 6	4 - 0 = 4	24
B	9 - 0 = 9	2 - (-1) = 3	27

Step 2: Compute overlap dimensions

Overlap width:

$$\min(3, 9) - \max(-3, 0)$$

$$3 - 0 = 3$$

Overlap height:

$$\min(4, 2) - \max(0, -1)$$

$$2 - 0 = 2$$

Variable	Value
overlapWidth	3
overlapHeight	2
overlapArea	6

Step 3: Compute final answer

$$24 + 27 - 6 = 45$$

Final output:

Example 2

Input:

ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2
bx1 = -2, by1 = -2, bx2 = 2, by2 = 2

Step 1: Compute rectangle areas

Rectangle	Width	Height	Area
A	4	4	16
B	4	4	16

Step 2: Compute overlap dimensions

Overlap width:

$$\min(2, 2) - \max(-2, -2) = 4$$

Overlap height:

$$\min(2, 2) - \max(-2, -2) = 4$$

Variable	Value
overlapWidth	4
overlapHeight	4
overlapArea	16

Step 3: Compute final answer

$$16 + 16 - 16 = 16$$

Final output:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a fixed number of arithmetic operations are performed
Space	O(1)	No extra data structures are used

The algorithm operates entirely through direct mathematical computation. Since the number of rectangles is fixed at two, the runtime does not depend on input size. Memory usage is also constant because only a handful of integer variables are stored.

Test Cases

solution = Solution()

# Provided example with partial overlap
assert solution.computeArea(-3, 0, 3, 4, 0, -1, 9, 2) == 45

# Identical rectangles
assert solution.computeArea(-2, -2, 2, 2, -2, -2, 2, 2) == 16

# No overlap
assert solution.computeArea(0, 0, 2, 2, 3, 3, 5, 5) == 8

# Touching edges only, no overlapping area
assert solution.computeArea(0, 0, 2, 2, 2, 0, 4, 2) == 8

# Touching corners only
assert solution.computeArea(0, 0, 2, 2, 2, 2, 4, 4) == 8

# One rectangle completely inside another
assert solution.computeArea(0, 0, 10, 10, 2, 2, 4, 4) == 100

# Negative coordinates with overlap
assert solution.computeArea(-5, -5, 0, 0, -3, -3, 2, 2) == 41

# Large coordinates near constraint limits
assert solution.computeArea(-10000, -10000, 10000, 10000,
                            -5000, -5000, 5000, 5000) == 400000000

# Thin vertical rectangles
assert solution.computeArea(0, 0, 1, 10, 0, 5, 1, 15) == 15

# Completely separate negative-coordinate rectangles
assert solution.computeArea(-10, -10, -5, -5,
                            5, 5, 10, 10) == 50

Test	Why
Partial overlap example	Validates standard overlap computation
Identical rectangles	Ensures duplicate area subtraction works correctly
No overlap	Confirms overlap clamps to zero
Touching edges	Verifies zero-width overlap handling
Touching corners	Verifies zero-area intersection handling
One rectangle inside another	Tests full containment
Negative coordinates	Ensures coordinate signs are handled correctly
Large coordinates	Confirms arithmetic correctness near limits
Thin rectangles	Tests narrow overlap dimensions
Separate negative rectangles	Ensures distant rectangles are summed correctly

Edge Cases

One important edge case occurs when the rectangles do not overlap at all. In this situation, the overlap width or height becomes negative. A buggy implementation might multiply these negative values and accidentally produce a positive overlap area. The solution prevents this by clamping overlap dimensions to zero using max(0, value).

Another critical case is when rectangles only touch at an edge or corner. Geometrically, touching boundaries do not create area overlap. For example, if one rectangle ends exactly where another begins, the overlap width becomes zero. Since zero multiplied by anything is zero, the implementation naturally handles this correctly.

A third important edge case is complete containment, where one rectangle lies entirely inside the other. In this scenario, the overlap area equals the smaller rectangle's entire area. The inclusion-exclusion formula still works perfectly because subtracting the overlap removes the duplicated counting exactly once.

Negative coordinates are also worth considering. Since rectangle dimensions are computed using coordinate differences, the actual coordinate sign does not matter. The implementation correctly handles rectangles in any quadrant of the plane.