LeetCode 939: Minimum Area Rectangle

Problem Restatement

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

Each point is represented as:

[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:

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

Function shape:

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

Examples

Example 1:

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

The points:

(1, 1), (1, 3), (3, 1), (3, 3)

form a rectangle.

Its width is:

3 - 1 = 2

Its height is:

3 - 1 = 2

Area:

2 * 2 = 4

So the answer is:

4

Example 2:

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

There are multiple rectangles.

One rectangle uses:

(3, 1), (3, 3), (4, 1), (4, 3)

Its width is 1.

Its height is 2.

Area:

2

So the answer is:

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:

(x1, y1)
(x2, y2)

If:

x1 != x2
y1 != y2

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

The other two required corners are:

(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:

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

Initialize:

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:

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

4. If yes, compute area:

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

5. Update the minimum.

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

Walkthrough

Use:

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

Store all points in a set.

Now choose diagonal pair:

(1, 1), (3, 3)

The other two corners must be:

(1, 3), (3, 1)

Both exist.

So we have a rectangle.

Area:

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

Now choose another pair, such as:

(1, 1), (2, 2)

The other corners would be:

(1, 2), (2, 1)

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

The minimum found is:

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:

(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:

n = len(points)

This is feasible for n <= 500.

Implementation

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:

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:

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

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

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

Then we check the missing corners:

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

If both exist, the area is:

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

Finally, if no rectangle was found:

return 0

Otherwise, return the best area.

Testing

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