# LeetCode 939: Minimum Area Rectangle

## Problem Restatement

We are given a list of unique points on a 2D plane.

Each point is represented as:

```python
[x, y]
```

We need to find the minimum area of a rectangle whose four corners are all in `points`.

The rectangle must have sides parallel to the X-axis and Y-axis.

So rotated rectangles do not count.

If no such rectangle exists, return:

```python
0
```

The official statement asks for the minimum area of an axis-aligned rectangle formed from the given points, or `0` if none exists. Constraints include `points.length <= 500`, all points unique, and coordinates up to `4 * 10^4`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A list of points `points` |
| Point format | `[x, y]` |
| Output | Minimum rectangle area |
| Rectangle rule | Sides must be parallel to the axes |
| Failure case | Return `0` |

Function shape:

```python
class Solution:
    def minAreaRect(self, points: list[list[int]]) -> int:
        ...
```

## Examples

Example 1:

```python
points = [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]]
```

The points:

```text
(1, 1), (1, 3), (3, 1), (3, 3)
```

form a rectangle.

Its width is:

```text
3 - 1 = 2
```

Its height is:

```text
3 - 1 = 2
```

Area:

```text
2 * 2 = 4
```

So the answer is:

```python
4
```

Example 2:

```python
points = [[1, 1], [1, 3], [3, 1], [3, 3], [4, 1], [4, 3]]
```

There are multiple rectangles.

One rectangle uses:

```text
(3, 1), (3, 3), (4, 1), (4, 3)
```

Its width is `1`.

Its height is `2`.

Area:

```python
2
```

So the answer is:

```python
2
```

## First Thought: Check Every Four Points

A direct solution is to choose every group of four points and test whether they form a valid axis-aligned rectangle.

This is too slow.

If there are `n` points, there are many possible groups of four. With `n = 500`, brute force over all quadruples is not practical.

We need to recognize rectangles using fewer points.

## Key Insight

An axis-aligned rectangle is determined by two opposite corners.

Suppose we choose two points:

```text
(x1, y1)
(x2, y2)
```

If:

```text
x1 != x2
y1 != y2
```

then these two points can be diagonal corners of an axis-aligned rectangle.

The other two required corners are:

```text
(x1, y2)
(x2, y1)
```

So the problem becomes:

For every possible diagonal pair, check whether the other two corners exist.

A hash set gives constant-time point lookup.

## Algorithm

Create a set of all points:

```python
point_set = {(x, y) for x, y in points}
```

Initialize:

```python
best = float("inf")
```

For every pair of points:

1. Let the points be `(x1, y1)` and `(x2, y2)`.
2. Skip the pair if `x1 == x2` or `y1 == y2`, because they cannot be diagonal corners.
3. Check whether both other corners exist:

```python
(x1, y2) in point_set
(x2, y1) in point_set
```

4. If yes, compute area:

```python
abs(x1 - x2) * abs(y1 - y2)
```

5. Update the minimum.

At the end, return `0` if no rectangle was found.

## Walkthrough

Use:

```python
points = [[1, 1], [1, 3], [3, 1], [3, 3], [2, 2]]
```

Store all points in a set.

Now choose diagonal pair:

```text
(1, 1), (3, 3)
```

The other two corners must be:

```text
(1, 3), (3, 1)
```

Both exist.

So we have a rectangle.

Area:

```text
abs(1 - 3) * abs(1 - 3) = 4
```

Now choose another pair, such as:

```text
(1, 1), (2, 2)
```

The other corners would be:

```text
(1, 2), (2, 1)
```

They do not exist, so this pair does not form a rectangle.

The minimum found is:

```python
4
```

## Correctness

Every axis-aligned rectangle has two diagonal corners with different x-coordinates and different y-coordinates.

When the algorithm checks that diagonal pair, it computes the two missing corners:

```text
(x1, y2)
(x2, y1)
```

If both are present, then the four points form exactly one axis-aligned rectangle. The algorithm computes its area and considers it for the minimum.

Conversely, whenever the algorithm finds two diagonal points and both missing corners exist, those four points form a valid axis-aligned rectangle. So every area considered by the algorithm belongs to a valid rectangle.

Since the algorithm checks every pair of points, it checks the diagonal pair of every valid rectangle. Therefore, it never misses any valid rectangle.

It returns the smallest area among all valid rectangles found. If no rectangle is found, it returns `0`.

So the algorithm is correct.

## Complexity

Let:

```python
n = len(points)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | We check every pair of points |
| Space | `O(n)` | We store all points in a set |

This is feasible for `n <= 500`.

## Implementation

```python
class Solution:
    def minAreaRect(self, points: list[list[int]]) -> int:
        point_set = {(x, y) for x, y in points}
        best = float("inf")

        n = len(points)

        for i in range(n):
            x1, y1 = points[i]

            for j in range(i + 1, n):
                x2, y2 = points[j]

                if x1 == x2 or y1 == y2:
                    continue

                if (x1, y2) in point_set and (x2, y1) in point_set:
                    area = abs(x1 - x2) * abs(y1 - y2)
                    best = min(best, area)

        if best == float("inf"):
            return 0

        return best
```

## Code Explanation

We first build a set of points:

```python
point_set = {(x, y) for x, y in points}
```

This lets us check whether a corner exists in expected constant time.

We try every pair of points:

```python
for i in range(n):
    for j in range(i + 1, n):
```

A valid diagonal pair must have different x and y coordinates:

```python
if x1 == x2 or y1 == y2:
    continue
```

Then we check the missing corners:

```python
if (x1, y2) in point_set and (x2, y1) in point_set:
```

If both exist, the area is:

```python
area = abs(x1 - x2) * abs(y1 - y2)
```

Finally, if no rectangle was found:

```python
return 0
```

Otherwise, return the best area.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.minAreaRect([
        [1, 1],
        [1, 3],
        [3, 1],
        [3, 3],
        [2, 2],
    ]) == 4

    assert s.minAreaRect([
        [1, 1],
        [1, 3],
        [3, 1],
        [3, 3],
        [4, 1],
        [4, 3],
    ]) == 2

    assert s.minAreaRect([
        [1, 1],
        [2, 2],
        [3, 3],
    ]) == 0

    assert s.minAreaRect([
        [0, 0],
        [0, 1],
        [1, 0],
        [1, 1],
    ]) == 1

    assert s.minAreaRect([
        [0, 0],
        [0, 2],
        [3, 0],
        [3, 2],
        [1, 0],
        [1, 2],
    ]) == 2

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard example 1 | Basic rectangle with extra point |
| Standard example 2 | Multiple rectangles, choose smaller |
| No rectangle | Must return `0` |
| Unit square | Minimum simple rectangle |
| Shared horizontal lines | Many rectangles, choose smallest |