LeetCode 963: Minimum Area Rectangle II

Problem Restatement

We are given a list of unique points in the x-y plane.

Each point is:

[x, y]

We need to find the minimum area of any rectangle formed by four of these points.

The rectangle sides do not need to be parallel to the axes. A rotated rectangle is allowed.

If no rectangle can be formed, return 0.

Answers within 10^-5 of the actual answer are accepted. The official constraints allow up to 50 unique points, with coordinates from 0 to 4 * 10^4.

Input and Output

Example function shape:

def minAreaFreeRect(points: list[list[int]]) -> float:
    ...

Examples

Example 1:

points = [[1, 2], [2, 1], [1, 0], [0, 1]]

Output:

2.00000

These four points form a rotated square with area 2.

Example 2:

points = [[0, 1], [2, 1], [1, 1], [1, 0], [2, 0]]

Output:

1.00000

The rectangle can be formed by:

[1, 0], [1, 1], [2, 1], [2, 0]

Its area is 1.

Example 3:

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

Output:

0

No rectangle can be formed.

First Thought: Pick Four Points

A direct approach is to try every group of four points and check whether they form a rectangle.

There are:

O(n^4)

groups.

Since n <= 50, this may still be large and awkward to implement correctly.

We need a cleaner geometry test.

Key Insight

A rectangle has a useful diagonal property.

For any rectangle:

1. The two diagonals have the same midpoint.
2. The two diagonals have the same length.

So instead of choosing four points directly, we can choose pairs of points as possible diagonals.

If two point pairs share the same midpoint and the same squared distance, then they are the diagonals of a rectangle.

Example:

A ----- B
|       |
D ----- C

The diagonals are:

A-C
B-D

They have the same midpoint and the same length.

This works for rotated rectangles too.

Avoiding Floating-Point Midpoints

Instead of storing the midpoint as:

((x1 + x2) / 2, (y1 + y2) / 2)

we store doubled midpoint coordinates:

x1 + x2
y1 + y2

This avoids floating-point precision issues.

We also store squared diagonal length:

(x1 - x2)^2 + (y1 - y2)^2

So each pair of points belongs to a group key:

(mid_x_sum, mid_y_sum, diagonal_length_squared)

Pairs in the same group are possible diagonal pairs of rectangles.

Computing Area

Suppose two diagonals are:

A-C
B-D

If they are in the same group, they form a rectangle.

To compute the area, choose one endpoint from the first diagonal, say A.

The two adjacent vertices are B and D.

The side lengths are:

distance(A, B)
distance(A, D)

So the rectangle area is:

distance(A, B) * distance(A, D)

where these are ordinary Euclidean distances.

To reduce square roots, compute squared side lengths first:

area = sqrt(side1_squared * side2_squared)

Algorithm

1. Create a dictionary:

groups[key] = list of point pairs

2. For every pair of points (p1, p2):
   • Compute doubled midpoint.
   • Compute squared distance.
   • Store the pair in its group.
3. For each group:
   • Try every two pairs in the group.
   • They represent two diagonals of a rectangle.
   • Compute the rectangle area.
   • Keep the minimum area.
4. If no rectangle was found, return 0.
5. Otherwise, return the minimum area.

Correctness

Every rectangle has two diagonals with the same midpoint and the same length. Therefore, when the algorithm groups all point pairs by doubled midpoint and squared distance, the two diagonals of any valid rectangle must appear in the same group.

Now consider two different point pairs in the same group. They have the same midpoint and the same diagonal length. A quadrilateral whose diagonals bisect each other is a parallelogram. A parallelogram whose diagonals have equal length is a rectangle. Therefore, these two pairs form a rectangle.

For each such pair of diagonals, the algorithm computes the area using two adjacent sides from one endpoint. This gives the exact rectangle area.

Since the algorithm considers every pair of points as a possible diagonal, it considers every possible rectangle. Since it keeps the minimum area among all found rectangles, the returned value is the minimum possible rectangle area.

If no two diagonal pairs share a valid group, then no rectangle exists, and returning 0 is correct.

Complexity

Let n = len(points).

With n <= 50, this is acceptable.

Implementation

from collections import defaultdict
from math import sqrt

class Solution:
    def minAreaFreeRect(self, points: list[list[int]]) -> float:
        n = len(points)
        groups = defaultdict(list)

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

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

                mid_x = x1 + x2
                mid_y = y1 + y2
                dist2 = (x1 - x2) ** 2 + (y1 - y2) ** 2

                key = (mid_x, mid_y, dist2)
                groups[key].append((x1, y1, x2, y2))

        best = float("inf")

        for pairs in groups.values():
            m = len(pairs)

            for i in range(m):
                ax, ay, cx, cy = pairs[i]

                for j in range(i + 1, m):
                    bx, by, dx, dy = pairs[j]

                    side1 = (ax - bx) ** 2 + (ay - by) ** 2
                    side2 = (ax - dx) ** 2 + (ay - dy) ** 2

                    area = sqrt(side1 * side2)
                    best = min(best, area)

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

        return best

Code Explanation

We group all point pairs as possible diagonals:

groups = defaultdict(list)

For each pair:

mid_x = x1 + x2
mid_y = y1 + y2
dist2 = (x1 - x2) ** 2 + (y1 - y2) ** 2

The key means:

same center and same diagonal length

Then:

groups[key].append((x1, y1, x2, y2))

stores that pair as a possible diagonal.

For every group, we compare two diagonals:

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

Take one endpoint from the first diagonal:

ax, ay

and both endpoints from the second diagonal:

(bx, by), (dx, dy)

These are adjacent vertices to A.

Compute squared side lengths:

side1 = (ax - bx) ** 2 + (ay - by) ** 2
side2 = (ax - dx) ** 2 + (ay - dy) ** 2

Then compute the area:

area = sqrt(side1 * side2)

Finally, return the best area found:

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

Testing

def run_tests():
    s = Solution()

    assert abs(
        s.minAreaFreeRect([[1, 2], [2, 1], [1, 0], [0, 1]]) - 2.0
    ) < 1e-5

    assert abs(
        s.minAreaFreeRect([[0, 1], [2, 1], [1, 1], [1, 0], [2, 0]]) - 1.0
    ) < 1e-5

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

    assert abs(
        s.minAreaFreeRect([[3, 1], [1, 1], [0, 1], [2, 1], [3, 3], [3, 2], [0, 2], [2, 3]]) - 2.0
    ) < 1e-5

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

    print("all tests passed")

run_tests()

Test meaning: