Minimum Area Rectangle II

MediumGeometry · Hashing🧩 Math & Geometry LeetCode #963 ↗Updated Oct 30, 2026

Problem

You are given distinct points points[i] = [x, y] in the plane. Find the smallest area of a rectangle whose four corners are all in the set. The rectangle may be rotated — its sides need not be parallel to the axes. Return 0 if no rectangle exists.

Input[[1,2],[2,1],[1,0],[0,1]]Output2.00000 (a tilted square)

Input[[0,1],[2,1],[1,1],[1,0],[2,0]]Output1.00000

Input[[0,3],[1,2],[3,1],[1,3],[2,1]]Output0

1 ≤ points.length ≤ 50 · 0 ≤ x, y ≤ 4·10⁴ · all points distinct · answers within 10^-5 are accepted

Try it yourself

Java

class Solution {
    public double minAreaFreeRect(int[][] points) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A quadrilateral is a rectangle exactly when its two diagonals share the same midpoint and the same length. So group all point pairs by (midpoint, length²); any two pairs in one group form a rectangle.

PatternMath & Geometry

Instinct Digits, factors, slopes or distances hide a formula - find the invariant, then guard against overflow, negatives and floating-point error.

Memory hack Mod peels, gcd reduces, squares compare - and long saves the day. Peel digits with %10, reduce slopes with gcd, compare squared distances.

Open the Math & Geometry guide →

Approaches

Brute ForceCheck Every 4-Point Combination

Time O(n⁴)Space O(1)

For each set of four points try the three ways to split them into two diagonals. If a split has equal midpoints and equal diagonal lengths it is a rectangle; its sides run from one corner to the two other-diagonal points, so area = |side₁| · |side₂|.

Java

public double minAreaFreeRect(int[][] points) {
    int n = points.length;
    double best = Double.MAX_VALUE;
    for (int a = 0; a < n; a++)
        for (int b = a + 1; b < n; b++)
            for (int c = b + 1; c < n; c++)
                for (int d = c + 1; d < n; d++) {
                    int[][] q = {points[a], points[b], points[c], points[d]};
                    // three ways to pair the 4 points as diagonals
                    int[][] splits = {{0, 1, 2, 3}, {0, 2, 1, 3}, {0, 3, 1, 2}};
                    for (int[] s : splits) {
                        double area = area(q[s[0]], q[s[1]], q[s[2]], q[s[3]]);
                        if (area > 0) best = Math.min(best, area);
                    }
                }
    return best == Double.MAX_VALUE ? 0 : best;
}

// area if (p,q) and (r,s) are the diagonals of a rectangle, else 0
private double area(int[] p, int[] q, int[] r, int[] s) {
    boolean sameMid = p[0] + q[0] == r[0] + s[0] && p[1] + q[1] == r[1] + s[1];
    if (!sameMid || dist2(p, q) != dist2(r, s)) return 0;
    return Math.sqrt(dist2(p, r)) * Math.sqrt(dist2(p, s));
}

private long dist2(int[] u, int[] v) {
    long dx = u[0] - v[0], dy = u[1] - v[1];
    return dx * dx + dy * dy;
}

Simple and exact; ~230k combinations for n = 50 is fine but scales badly.

BetterFix a Right-Angle Corner + Hash Set

Time O(n³)Space O(n)

Pick a corner p and two other points q, r. If (q-p)·(r-p) = 0 the angle at p is 90°, and the fourth corner is forced: q + r - p. One hash-set lookup decides whether the rectangle exists; its area is |q-p| · |r-p|.

Java

public double minAreaFreeRect(int[][] points) {
    Set<Long> seen = new HashSet<>();
    for (int[] p : points) seen.add(key(p[0], p[1]));
    int n = points.length;
    double best = Double.MAX_VALUE;
    for (int[] p : points) {
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int[] q = points[i], r = points[j];
                if (q == p || r == p) continue;
                long ux = q[0] - p[0], uy = q[1] - p[1];
                long vx = r[0] - p[0], vy = r[1] - p[1];
                if (ux * vx + uy * vy != 0) continue; // not a right angle at p
                if (!seen.contains(key(q[0] + r[0] - p[0], q[1] + r[1] - p[1]))) continue;
                double area = Math.sqrt(ux * ux + uy * uy) * Math.sqrt(vx * vx + vy * vy);
                best = Math.min(best, area);
            }
        }
    }
    return best == Double.MAX_VALUE ? 0 : best;
}

private long key(long x, long y) {
    return x * 200_001L + y; // unique for the coordinate range, even off-grid
}

Drops a factor of n by computing the 4th corner instead of searching for it.

OptimalGroup Diagonals by (Midpoint, Length)

Time O(n³) worst, ~O(n²) typicalSpace O(n²)

Treat every pair as a potential diagonal and bucket it by (x1+x2, y1+y2, length²) — using sums avoids fractional midpoints. Two pairs in the same bucket are the diagonals of a rectangle. A point can appear at most once per bucket, so a bucket holds ≤ n/2 pairs and the total pair-of-pairs work is O(n³) at worst, usually near O(n²).

Java

public double minAreaFreeRect(int[][] points) {
    int n = points.length;
    Map<String, List<int[]>> groups = new HashMap<>();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int[] p = points[i], q = points[j];
            String k = (p[0] + q[0]) + "," + (p[1] + q[1]) + "," + dist2(p, q);
            groups.computeIfAbsent(k, z -> new ArrayList<>()).add(new int[]{i, j});
        }
    }
    double best = Double.MAX_VALUE;
    for (List<int[]> diagonals : groups.values()) {
        for (int a = 0; a < diagonals.size(); a++) {
            for (int b = a + 1; b < diagonals.size(); b++) {
                int[] p = points[diagonals.get(a)[0]];
                int[] r = points[diagonals.get(b)[0]], s = points[diagonals.get(b)[1]];
                // sides of the rectangle meet at corner p
                double area = Math.sqrt(dist2(p, r)) * Math.sqrt(dist2(p, s));
                best = Math.min(best, area);
            }
        }
    }
    return best == Double.MAX_VALUE ? 0 : best;
}

private long dist2(int[] u, int[] v) {
    long dx = u[0] - v[0], dy = u[1] - v[1];
    return dx * dx + dy * dy;
}

The standard answer: one hashing pass, then only genuine rectangles are examined.

Pro tip

Keep every comparison in integers (coordinate sums, squared lengths) and take the square root only for the final area — no floating-point keys.

At a glance

Level	Approach	Time	Space
Brute Force	Check Every 4-Point Combination	`O(n⁴)`	`O(1)`
Better	Fix a Right-Angle Corner + Hash Set	`O(n³)`	`O(n)`
Optimal	Group Diagonals by (Midpoint, Length)	`O(n³) worst, ~O(n²) typical`	`O(n²)`

Common pitfalls

Using floating-point midpoints as map keys — use coordinate sums instead.
Equal midpoints alone give a parallelogram; the diagonals must also have equal length.
Squared distances up to 3.2·10⁹ overflow int — use long.

Interview tips

State the rectangle test (equal, bisecting diagonals) before touching code.
Mention the O(n³) right-angle method as a solid fallback if hashing feels risky.
Explain how the area comes from two adjacent sides meeting at one corner.

Pattern

Geometry + hashing invariants → shape detection from a point set; hash an invariant (midpoint, length, slope) of point pairs.

My notes saved in this browser