# LeetCode 223: Rectangle Area

## Problem Restatement

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

The first rectangle is defined by:

```python
(ax1, ay1)
(ax2, ay2)
```

The second rectangle is defined by:

```python
(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

| Item | Meaning |
|---|---|
| Input | Eight integers describing two rectangles |
| Output | Total covered area |
| Rectangle A | Bottom-left `(ax1, ay1)`, top-right `(ax2, ay2)` |
| Rectangle B | Bottom-left `(bx1, by1)`, top-right `(bx2, by2)` |
| Important case | Overlap must be counted once |

Example function shape:

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

## Examples

Example 1:

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

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

Area of rectangle A:

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

Area of rectangle B:

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

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

Overlap area:

```text
3 * 2 = 6
```

Total covered area:

```text
24 + 27 - 6 = 45
```

Answer:

```python
45
```

Example 2:

```python
ax1 = -2
ay1 = -2
ax2 = 2
ay2 = 2

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

The rectangles are identical.

Each area is:

```text
4 * 4 = 16
```

The overlap is also `16`.

Total:

```text
16 + 16 - 16 = 16
```

Answer:

```python
16
```

## First Thought

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

```text
area A + area B
```

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

So the correct formula is:

```text
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)`:

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

So:

```python
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:

```python
overlap_left = max(ax1, bx1)
```

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

```python
overlap_right = min(ax2, bx2)
```

So the overlap width is:

```python
overlap_width = overlap_right - overlap_left
```

Similarly for the y-axis:

```python
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:

```python
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:

```text
area_a + area_b - overlap_area
```

## Walkthrough

Use:

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

Rectangle A:

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

Rectangle B:

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

Overlap x-range:

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

Overlap y-range:

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

Overlap area:

```text
3 * 2 = 6
```

Final answer:

```text
24 + 27 - 6 = 45
```

## Touching Edges

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

Example:

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

Overlap width:

```text
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:

```text
area_a + area_b - overlap_area
```

is exactly the total area covered by the two rectangles.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(1)` | Only a fixed number of arithmetic operations |
| Space | `O(1)` | Only a fixed number of variables |

## Implementation

```python
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:

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

Compute the second rectangle's area:

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

Compute possible overlap width:

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

Compute possible overlap height:

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

Clamp negative values to zero:

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

Compute overlap area:

```python
overlap_area = overlap_width * overlap_height
```

Subtract the overlap once:

```python
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.

```python
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

```python
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()
```

| Test | Why |
|---|---|
| Standard example | Partial overlap |
| Identical rectangles | Full overlap |
| Touching edge | Zero overlap area |
| Separate rectangles | No overlap |
| One rectangle inside another | Inner area counted once |
| Diagonal overlap | Partial overlap on both axes |