LeetCode 963 - Minimum Area Rectangle II

The problem gives us a collection of unique points on a 2D plane. Our task is to determine the minimum possible area of any rectangle that can be formed using exactly four of these points as vertices.

leetcodemediumarrayhash-tablemathgeometry

LeetCode Problem 963

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Geometry

Solution

Problem Understanding

The problem gives us a collection of unique points on a 2D plane. Our task is to determine the minimum possible area of any rectangle that can be formed using exactly four of these points as vertices.

The important detail is that the rectangle does not need to be aligned with the coordinate axes. This makes the problem significantly harder than the standard axis-aligned rectangle problem. A valid rectangle may be rotated at any angle.

The input is an array points, where each element is a pair [x, y] representing the coordinates of a point. The output should be the smallest rectangle area that can be formed from any four points in the set. If no rectangle exists, we return 0.

A rectangle in geometry has several important properties:

  • Opposite sides are parallel and equal in length
  • Adjacent sides are perpendicular
  • The diagonals bisect each other
  • The diagonals are equal in length

The diagonal properties are especially useful for this problem.

The constraints are relatively small:

  • At most 50 points
  • Coordinates up to 4 * 10^4
  • All points are unique

Because the number of points is small, algorithms with quadratic or cubic behavior are feasible. However, brute-force enumeration over all quadruples becomes expensive because there can be:

$\binom{50}{4}$

possible groups of four points, which is too many for repeated geometric validation.

Several edge cases are important:

  • Fewer than four points, no rectangle can exist
  • Points may form parallelograms that are not rectangles
  • Multiple rectangles may exist, we need the minimum area
  • Rotated rectangles must be handled correctly
  • Floating point precision matters because areas may not be integers
  • Degenerate rectangles with zero area must not be counted

Approaches

Brute Force Approach

The most direct solution is to examine every possible set of four points and determine whether those four points form a rectangle.

For each quadruple:

  1. Compute all six pairwise distances
  2. Check whether the points satisfy rectangle properties
  3. If valid, compute the area
  4. Track the minimum area

This works because every rectangle consists of exactly four vertices, so checking all quadruples guarantees we eventually find the optimal rectangle.

The challenge is efficiency. There are:

$O(n^4)$

possible quadruples. Even with only 50 points, this becomes expensive, especially since each quadruple requires additional geometric computations.

Key Insight for the Optimal Solution

The crucial observation is that rectangles have equal diagonals that share the same midpoint.

If two pairs of points represent the diagonals of the same rectangle, then:

  • Their midpoints are identical
  • Their diagonal lengths are identical

This gives us a much more efficient strategy.

Instead of directly searching for rectangles, we:

  1. Enumerate every pair of points
  2. Treat each pair as a potential diagonal
  3. Group diagonals by:
  • midpoint
  • squared length
  1. Any two diagonals in the same group can potentially form a rectangle

Once we identify two compatible diagonals, we can reconstruct the rectangle and compute its area.

This reduces the search space dramatically because we leverage geometric properties instead of brute-force validation.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^4) O(1) Checks every quadruple explicitly
Optimal O(n^2 + k^2) O(n^2) Groups diagonals by midpoint and length

Here, k represents the number of diagonals in a group. In practice, this approach is dramatically faster.

Algorithm Walkthrough

  1. Iterate through every pair of points.

Each pair of points may represent a diagonal of a rectangle. For every pair (i, j), compute:

  • the midpoint
  • the squared diagonal length

We use squared distance instead of actual distance because square roots are unnecessary for equality checks. 2. Store diagonals in a hash map.

The hash map key consists of:

  • midpoint x-coordinate
  • midpoint y-coordinate
  • squared diagonal length

Two diagonals belong to the same rectangle candidate group only if all three values match.

The value stored for each key is a list of point pairs representing diagonals. 3. Process each diagonal group.

If a group contains multiple diagonals, then every pair of diagonals in that group can potentially form a rectangle.

Suppose we have diagonals:

  • (A, C)
  • (B, D)

These four points may form a rectangle. 4. Compute rectangle area.

Choose one endpoint from the first diagonal as a reference point.

Then compute the lengths of two adjacent sides using Euclidean distance.

If:

  • A
  • B
  • D

are three rectangle vertices, then:

  • side1 = distance(A, B)
  • side2 = distance(A, D)

The rectangle area is:

$\text{Area} = |AB| \times |AD|$

  1. Track the minimum area.

Update the global minimum whenever a smaller valid rectangle area is found. 2. Return the result.

If no rectangle was discovered, return 0.

Why it works

The correctness relies on a fundamental rectangle property:

  • Rectangles have diagonals with equal lengths
  • Rectangles have diagonals sharing the same midpoint

Therefore, any rectangle must produce two diagonal pairs grouped together in our hash map.

Conversely, whenever two diagonals share the same midpoint and length, the four endpoints form a parallelogram with equal diagonals, which guarantees the shape is a rectangle.

Thus, every valid rectangle is discovered exactly through these diagonal groups.

Python Solution

from typing import List
from collections import defaultdict
from math import sqrt

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

        diagonals = defaultdict(list)

        # Store all possible diagonals
        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

                dist_sq = (x1 - x2) ** 2 + (y1 - y2) ** 2

                diagonals[(mid_x, mid_y, dist_sq)].append(
                    (x1, y1, x2, y2)
                )

        min_area = float("inf")

        # Process groups with same midpoint and diagonal length
        for group in diagonals.values():
            m = len(group)

            for i in range(m):
                x1, y1, x2, y2 = group[i]

                for j in range(i + 1, m):
                    x3, y3, x4, y4 = group[j]

                    # Use one point as reference
                    side1 = sqrt((x1 - x3) ** 2 + (y1 - y3) ** 2)
                    side2 = sqrt((x1 - x4) ** 2 + (y1 - y4) ** 2)

                    area = side1 * side2

                    if area > 0:
                        min_area = min(min_area, area)

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

The implementation begins by iterating through every pair of points. Each pair is treated as a potential rectangle diagonal.

For every diagonal, the algorithm computes:

  • midpoint
  • squared distance

The midpoint is stored as (x1 + x2, y1 + y2) instead of dividing by two. This avoids floating point precision issues while preserving uniqueness.

The hash map groups together diagonals that could belong to the same rectangle.

After all diagonals are collected, the algorithm examines every pair of diagonals inside each group. Because those diagonals share both midpoint and length, they define a rectangle.

To compute the rectangle area, the implementation chooses one endpoint from the first diagonal and computes distances to the endpoints of the second diagonal. These become the rectangle side lengths.

The minimum non-zero area is tracked and returned.

Go Solution

package main

import (
	"math"
	"strconv"
)

func minAreaFreeRect(points [][]int) float64 {
	n := len(points)

	diagonals := make(map[string][][4]int)

	// Store all diagonals
	for i := 0; i < n; i++ {
		x1, y1 := points[i][0], points[i][1]

		for j := i + 1; j < n; j++ {
			x2, y2 := points[j][0], points[j][1]

			midX := x1 + x2
			midY := y1 + y2

			distSq := (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)

			key := strconv.Itoa(midX) + "," +
				strconv.Itoa(midY) + "," +
				strconv.Itoa(distSq)

			diagonals[key] = append(
				diagonals[key],
				[4]int{x1, y1, x2, y2},
			)
		}
	}

	minArea := math.Inf(1)

	for _, group := range diagonals {
		m := len(group)

		for i := 0; i < m; i++ {
			x1, y1 := group[i][0], group[i][1]

			for j := i + 1; j < m; j++ {
				x3, y3 := group[j][0], group[j][1]
				x4, y4 := group[j][2], group[j][3]

				side1 := math.Sqrt(
					float64((x1-x3)*(x1-x3) + (y1-y3)*(y1-y3)),
				)

				side2 := math.Sqrt(
					float64((x1-x4)*(x1-x4) + (y1-y4)*(y1-y4)),
				)

				area := side1 * side2

				if area > 0 {
					minArea = math.Min(minArea, area)
				}
			}
		}
	}

	if math.IsInf(minArea, 1) {
		return 0
	}

	return minArea
}

The Go implementation follows the same geometric logic as the Python version.

A few Go-specific details are important:

  • Go does not support tuples as hash keys directly in the same convenient way as Python, so the implementation builds a string key from midpoint and squared distance.
  • math.Sqrt operates on float64, so integer expressions must be converted.
  • math.Inf(1) is used to initialize the minimum area.
  • Fixed-size arrays [4]int are used for compact diagonal storage.

Worked Examples

Example 1

Input:

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

These points form a rotated square.

Step 1: Generate diagonals

Pair Midpoint Distance Squared
(1,2)-(1,0) (2,2) 4
(2,1)-(0,1) (2,2) 4

Both diagonals share:

  • same midpoint
  • same length

So they belong to the same group.

Step 2: Compute area

Choose point (1,2).

Distances:

Side Length
to (2,1) √2
to (0,1) √2

Area:

$\sqrt{2} \times \sqrt{2} = 2$

Minimum area becomes 2.

Example 2

Input:

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

The rectangle is axis-aligned:

  • (1,0)
  • (1,1)
  • (2,1)
  • (2,0)

Diagonals

Diagonal Midpoint Distance Squared
(1,0)-(2,1) (3,1) 2
(1,1)-(2,0) (3,1) 2

Area Calculation

Side Length
vertical 1
horizontal 1

Area:

$1 \times 1 = 1$

Example 3

Input:

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

No pair of diagonals share both:

  • midpoint
  • equal length

Therefore no rectangle exists.

Return 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2 + g^2) Generate all diagonals, then compare diagonal pairs inside groups
Space O(n^2) Stores all diagonals in the hash map

The algorithm generates all point pairs, which requires:

$O(n^2)$

time and space.

In the second phase, each diagonal group is processed pairwise. In the worst case many diagonals could fall into the same group, though with only 50 points this remains practical.

Overall, the solution is efficient enough for the constraints and dramatically faster than brute-force rectangle enumeration.

Test Cases

from typing import List

s = Solution()

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

# Example 2, axis-aligned rectangle
assert abs(
    s.minAreaFreeRect([[0,1],[2,1],[1,1],[1,0],[2,0]]) - 1.0
) < 1e-5

# Example 3, no rectangle
assert abs(
    s.minAreaFreeRect([[0,3],[1,2],[3,1],[1,3],[2,1]]) - 0.0
) < 1e-5

# Minimum input size
assert abs(
    s.minAreaFreeRect([[0,0]]) - 0.0
) < 1e-5

# Two points only
assert abs(
    s.minAreaFreeRect([[0,0],[1,1]]) - 0.0
) < 1e-5

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

# Larger rectangle
assert abs(
    s.minAreaFreeRect([[0,0],[4,0],[4,3],[0,3]]) - 12.0
) < 1e-5

# Multiple rectangles, choose minimum
assert abs(
    s.minAreaFreeRect([
        [0,0],[1,0],[1,1],[0,1],
        [0,2],[2,0],[2,2]
    ]) - 1.0
) < 1e-5

# Rotated rectangle with non-integer sides
assert abs(
    s.minAreaFreeRect([
        [1,2],[2,1],[3,2],[2,3]
    ]) - 2.0
) < 1e-5

# Collinear points only
assert abs(
    s.minAreaFreeRect([
        [0,0],[1,0],[2,0],[3,0]
    ]) - 0.0
) < 1e-5
Test Why
Rotated rectangle Verifies non-axis-aligned handling
Axis-aligned rectangle Confirms standard rectangles work
No rectangle Ensures invalid inputs return zero
Single point Minimum boundary condition
Two points Insufficient vertices
Unit square Basic valid rectangle
Larger rectangle Confirms larger area calculation
Multiple rectangles Ensures minimum area selection
Rotated diamond Tests geometric correctness
Collinear points Prevents degenerate rectangles

Edge Cases

One important edge case occurs when there are fewer than four points. A rectangle requires exactly four vertices, so any input with fewer than four points must return 0. The implementation naturally handles this because no valid diagonal pairs can ever be formed.

Another subtle edge case involves parallelograms that are not rectangles. A naive geometric solution might incorrectly classify them as valid rectangles. The diagonal grouping method avoids this issue because only parallelograms with equal diagonals are rectangles. Matching midpoint alone is not sufficient, equal diagonal length is also required.

Floating point precision is another common source of bugs. Rectangle areas may involve irrational numbers because rotated rectangles often have diagonal side lengths. The implementation minimizes precision issues by using squared distances for grouping and only applying square roots during final area computation.

Degenerate rectangles with zero area must also be excluded. This can happen if points overlap conceptually during diagonal pairing or if side lengths collapse to zero. The implementation explicitly checks area > 0 before updating the minimum.