Minimum Area Rectangle II: Diagonal-Based Geometry

LeetCode 963, Minimum Area Rectangle II, asks you to find the minimum area of any rectangle that can be formed from a set of points in the XY plane. Unlike the original Minimum Area Rectangle (LeetCode 939), the rectangle does not have to be axis-aligned. It can be tilted at any angle.

The problem

You are given an array of points in the plane. Return the minimum area of any rectangle formed by some of these points, with sides not necessarily parallel to the axes. If no rectangle can be formed, return 0. The answer should be accurate within 1e-5.

For example, given points = [[1,2],[2,1],[1,0],[0,1]], the four points form a diamond-shaped rectangle (a square rotated 45 degrees) with area 2.0.

Why this problem matters

This problem forces you to think beyond the axis-aligned case. In LeetCode 939, two diagonal corners uniquely determine the other two corners because sides must be parallel to the axes. That trick breaks down here because a tilted rectangle has infinitely many possible orientations.

The real challenge is finding a property that is shared by all rectangles, regardless of orientation, and that you can compute efficiently from pairs of points. The answer lies in the diagonals.

Every rectangle has two diagonals, and those diagonals always bisect each other (they share the same midpoint) and have the same length. This is a geometric invariant that holds for axis-aligned rectangles, tilted rectangles, and even degenerate ones. If you can find two pairs of points that share the same diagonal midpoint and the same diagonal length, those four points form a rectangle.

The brute force approach

The naive approach checks all combinations of four points. For each 4-point combination, you verify whether they form a valid rectangle (check all pairwise distances and angles). This runs in O(n^4) time, which is far too slow when n can be up to 50. Even with n = 50, that is roughly 230,000 combinations, and each requires non-trivial geometric checks.

We need a smarter way to identify which sets of four points actually form rectangles.

The key insight

Two diagonals of a rectangle always share the same midpoint and have the same length. This means we can group pairs of points by their midpoint and distance. Any two pairs in the same group can potentially form a rectangle.

Walking through it step by step

The solution

from collections import defaultdict
import math

class Solution:
    def minAreaFreeRect(self, points: list[list[int]]) -> float:
        n = len(points)
        point_set = set(map(tuple, points))
        # Group pairs by (center, distance_squared)
        diag_map = defaultdict(list)

        for i in range(n):
            for j in range(i + 1, n):
                cx = points[i][0] + points[j][0]
                cy = points[i][1] + points[j][1]
                # Use sum instead of dividing by 2 to avoid floats in key
                d2 = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2
                diag_map[(cx, cy, d2)].append((i, j))

        min_area = float("inf")
        for key, pairs in diag_map.items():
            for a in range(len(pairs)):
                i1, j1 = pairs[a]
                for b in range(a + 1, len(pairs)):
                    i2, j2 = pairs[b]
                    # Four points: points[i1], points[j1], points[i2], points[j2]
                    p1 = points[i1]
                    p2 = points[i2]
                    p3 = points[j1]
                    # Compute area using cross product of two adjacent sides
                    v1 = (p2[0] - p1[0], p2[1] - p1[1])
                    v2 = (p3[0] - p1[0], p3[1] - p1[1])
                    area = abs(v1[0] * v2[1] - v1[1] * v2[0])
                    if area > 0:
                        min_area = min(min_area, area)

        return min_area if min_area != float("inf") else 0.0

The algorithm has two phases. First, it groups all pairs of points by their diagonal signature (the sum of coordinates and the squared distance). Using the coordinate sum instead of the actual midpoint avoids floating-point keys. Second, for each group with at least two pairs, it tries all combinations of two pairs and computes the area of the resulting rectangle using the cross product. The cross product of two adjacent sides gives the area of the parallelogram they span, which equals the rectangle area since the four points form a valid rectangle.

Complexity analysis

Time: The outer double loop over all pairs is O(n^2). The grouping step uses a hash map with O(n^2) total entries. For each group, you iterate over pairs of pairs. In the worst case (all pairs share the same center and distance), this could be O(n^2) per group, but in practice the groups are small. The total work across all groups is bounded by O(n^2) amortized for typical inputs.

Space: The hash map stores up to O(n^2) pairs (one entry per pair of points), and each group stores references to its pairs.

Building blocks

1. Diagonal midpoint grouping

The core technique is recognizing that the midpoint and length of a diagonal are invariants shared by both diagonals of any rectangle. By computing these for every pair and grouping by them, you reduce the search space from all 4-point combinations to just pairs within each group:

cx = points[i][0] + points[j][0]  # 2 * midpoint_x
cy = points[i][1] + points[j][1]  # 2 * midpoint_y
d2 = (points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2

Using the sum of coordinates (rather than dividing by 2) avoids floating-point keys in the hash map. This is a common trick when you need exact comparisons of midpoints.

2. Cross product for area computation

Given three points P1, P2, P3 that form a corner of the rectangle at P1, the area is:

area = abs((P2.x - P1.x) * (P3.y - P1.y) - (P2.y - P1.y) * (P3.x - P1.x))

This is the absolute value of the cross product of vectors P1P2 and P1P3. It gives the area of the parallelogram formed by those two vectors, which equals the rectangle area when the four points form a valid rectangle.

Edge cases

• Fewer than 4 points: No rectangle can be formed. Return 0.
• No valid rectangle: If no two pairs share the same midpoint and distance, no rectangle exists. Return 0.
• Degenerate rectangles: If the four points are collinear, the cross product is 0, so the area check (area > 0) filters these out.
• Duplicate points: Pairs involving the same point twice produce zero-length diagonals. The area computation naturally produces 0 for these, and the area > 0 check skips them.
• Multiple rectangles with the same area: The algorithm correctly tracks the minimum across all valid rectangles.
• Floating-point precision: The problem asks for accuracy within 1e-5. Since all input coordinates are integers, the cross product area is always an integer, so precision is not an issue.

Common mistakes

1. Using floating-point midpoints as hash keys. Floating-point arithmetic can produce slightly different values for coordinates that should be equal. Using the sum of coordinates (integers) instead of dividing by 2 avoids this entirely.

2. Forgetting the axis-aligned case. The algorithm handles axis-aligned rectangles automatically, since their diagonals also share midpoints and lengths. No special case is needed.

3. Not filtering zero-area results. Four points can share the same diagonal midpoint and distance but be collinear, producing a degenerate "rectangle" with area 0. Always check that the computed area is positive.

4. Confusing this with LeetCode 939. The axis-aligned version uses a completely different approach (checking if opposite corners exist in a set). That approach does not work here because the other two corners of a tilted rectangle cannot be derived from just two diagonal corners.

5. Using distance instead of distance squared. Taking square roots introduces floating-point errors in the grouping key. Use the squared distance to keep everything in integer arithmetic.

From understanding to recall

The diagonal midpoint property is the single insight that makes this problem tractable. Once you internalize that two diagonals of a rectangle must share the same midpoint and length, the algorithm writes itself: group pairs, iterate groups, compute areas. The cross product for area is a standard geometry tool you will use in many other problems.

Spaced repetition is the most effective way to lock in this pattern. You practice the diagonal grouping, the coordinate-sum trick for integer keys, and the cross product area formula from scratch. After a few reps, you see "non-axis-aligned rectangle" and immediately reach for diagonal midpoint grouping. No re-derivation needed.

Related posts

• Minimum Area Rectangle - The axis-aligned version of this problem
• Max Points on a Line - Another geometry problem using point relationships
• Rectangle Area - Computing areas with coordinate geometry

The diagonal midpoint approach and the cross product area formula are two of the reusable building blocks that CodeBricks drills independently. Learning them separately and practicing with spaced repetition means you can assemble solutions to new geometry problems on the fly, rather than memorizing entire solutions for individual problems.