LeetCode 223: Rectangle Area Solution in Python Explained

Problem Statement

In LeetCode 223: Rectangle Area, you’re given:

• Coordinates of two rectangles in the format (ax1, ay1, ax2, ay2) and (bx1, by1, bx2, by2), where (x1, y1) is the bottom-left corner and (x2, y2) is the top-right corner.
• Your task is to return the total area covered by both rectangles, including overlap only once.

The rectangles are axis-aligned (sides parallel to x and y axes). This differs from tree node counting in LeetCode 222: Count Complete Tree Nodes, focusing instead on geometric area computation.

Constraints

• -10⁴ ≤ ax1, ay1, ax2, ay2, bx1, by1, bx2, by2 ≤ 10⁴.
• ax1 < ax2 and ay1 < ay2.
• bx1 < bx2 and by1 < by2.

Examples

Let’s see some cases:

Copy codeInput: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45
Explanation:
<ul>
<li>Rectangle A: Area = 6 * 4 = 24.</li>
<li>Rectangle B: Area = 9 * 3 = 27.</li>
<li>Overlap: (0 to 3, 0 to 2) = 3 * 2 = 6.</li>
<li>Total = 24 + 27 - 6 = 45.</li>
</ul>

Copy codeInput: ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2
Output: 16
Explanation: Identical rectangles, area = 4 * 4 = 16, overlap = 16, total = 16.

Copy codeInput: ax1 = -1, ay1 = -1, ax2 = 1, ay2 = 1, bx1 = 2, by1 = 2, bx2 = 4, by2 = 4
Output: 8
Explanation: No overlap, total = 2 * 2 + 2 * 2 = 8.

These examples show we’re summing areas and subtracting overlap.

Understanding the Problem

How do we solve LeetCode 223: Rectangle Area in Python? For the first example, we calculate each rectangle’s area and subtract their overlap. A naive approach might scan all points (impractical), but geometric reasoning simplifies it. This isn’t a duplicate check like LeetCode 220: Contains Duplicate III; it’s about coordinate-based area calculation. We’ll use: 1. Geometric Overlap Calculation: O(1) time, O(1) space—our best solution. 2. Brute Force with Grid: O(mn) time, O(mn) space—an alternative (m, n = grid dimensions).

Let’s dive into the best solution.

Best Solution: Geometric Overlap Calculation Approach

Explanation

The Geometric Overlap Calculation approach uses coordinate math:

• Compute individual areas: area1 = (ax2 - ax1) * (ay2 - ay1), area2 = (bx2 - bx1) * (by2 - by1).
• Find overlap:
• X overlap: max(0, min(ax2, bx2) - max(ax1, bx1)).
• Y overlap: max(0, min(ay2, by2) - max(ay1, by1)).
• Overlap area = X overlap * Y overlap.
• Total area = area1 + area2 - overlap.

This runs in O(1) time (constant operations) and O(1) space, making it optimal—our best solution.

For [-3,0,3,4] and [0,-1,9,2], it computes areas and overlap directly.

Step-by-Step Example

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

Goal: Return 45.

• Step 1: Calculate individual areas.
• Rectangle A: (3 - (-3)) * (4 - 0) = 6 * 4 = 24.
• Rectangle B: (9 - 0) * (2 - (-1)) = 9 * 3 = 27.
• Step 2: Compute overlap.
• X overlap: min(3, 9) - max(-3, 0) = 3 - 0 = 3.
• Y overlap: min(4, 2) - max(0, -1) = 2 - 0 = 2.
• Overlap area: 3 * 2 = 6.
• Step 3: Total area.
• 24 + 27 - 6 = 45.
• Output: 45.

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

Goal: Return 16.

• Step 1: Areas: 4 * 4 = 16, 4 * 4 = 16.
• Step 2: Overlap: X = 2 - (-2) = 4, Y = 2 - (-2) = 4, area = 4 * 4 = 16.
• Step 3: 16 + 16 - 16 = 16.
• Output: 16.

How the Code Works (Geometric Overlap Calculation) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codedef computeArea(ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:
    # Line 1: Calculate individual areas
    area1 = (ax2 - ax1) * (ay2 - ay1)
    # First rectangle area (e.g., 6 * 4 = 24)
    area2 = (bx2 - bx1) * (by2 - by1)
    # Second rectangle area (e.g., 9 * 3 = 27)

    # Line 2: Compute overlap in x-direction
    x_overlap = max(0, min(ax2, bx2) - max(ax1, bx1))
    # Overlapping x length (e.g., min(3,9)-max(-3,0)=3)

    # Line 3: Compute overlap in y-direction
    y_overlap = max(0, min(ay2, by2) - max(ay1, by1))
    # Overlapping y length (e.g., min(4,2)-max(0,-1)=2)

    # Line 4: Calculate overlap area
    overlap = x_overlap * y_overlap
    # Overlap area (e.g., 3 * 2 = 6)

    # Line 5: Return total area
    return area1 + area2 - overlap
    # Total area (e.g., 24 + 27 - 6 = 45)

This solution is concise and uses geometric logic effectively.

Alternative: Brute Force with Grid Approach

Explanation

The Brute Force with Grid approach simulates the plane:

• Create a grid covering the range of both rectangles.
• Mark cells covered by each rectangle.
• Count unique covered cells.

It’s O(mn) time and space (m, n = grid dimensions), intuitive but impractical for large ranges.

Step-by-Step Example

For [-2,-2,2,2] and [0,0,4,4]:

• Grid: -2 to 4 (x), -2 to 4 (y), 7×7.
• Mark A: (-2,-2) to (2,2), 16 cells.
• Mark B: (0,0) to (4,4), 16 cells.
• Overlap: (0,0) to (2,2), 4 cells.
• Total: 16 + 16 - 4 = 28.
• Output: 28.

How the Code Works (Brute Force)

Copy codedef computeAreaBrute(ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:
    grid = set()
    for x in range(ax1, ax2):
        for y in range(ay1, ay2):
            grid.add((x, y))
    for x in range(bx1, bx2):
        for y in range(by1, by2):
            grid.add((x, y))
    return len(grid)

Complexity

• Geometric Overlap Calculation:
• Time: O(1) – constant operations.
• Space: O(1) – no extra space.
• Brute Force with Grid:
• Time: O(mn) – grid size (m, n = width, height).
• Space: O(mn) – set storage.

Efficiency Notes

Geometric Overlap Calculation is our best solution with O(1) time, perfect for this problem. Brute Force is illustrative but inefficient due to large coordinate ranges.

Key Insights

• Overlap: Subtract once.
• Geometry: Simplifies computation.
• Axis-Aligned: Enables direct formulas.

Additional Example

For [-1,-1,1,1] and [2,2,4,4]:

• Geometric: 4 + 4 - 0 = 8.
• Brute: Same via grid.

Edge Cases

• No overlap: Sum of areas.
• Identical: One area.
• Negative coords: Handled by formulas.

Both work correctly.

Final Thoughts

LeetCode 223: Rectangle Area in Python is a neat geometric challenge. Geometric Overlap Calculation excels in speed, while Brute Force offers a visual approach. Want more? Try LeetCode 84: Largest Rectangle in Histogram or LeetCode 221: Maximal Square. Test your skills—Solve LeetCode 223 on LeetCode with [-3,0,3,4,0,-1,9,2] (expecting 45)—calculate that area today!