Minimum Area Rectangle

Tags

Minimum Area Rectangle

Category

Arrays

Difficulty

Very Hard

Problem Statement

Given a set of points in the 2D plane, find the minimum area of a rectangle that can be formed using any four of the given points as its corners. The rectangle sides do not need to be parallel to the axes. If no rectangle can be formed, return 0.

Intuition

For axis-aligned rectangles, we can check pairs of diagonal points. For arbitrary rectangles (not axis-aligned), the key geometric property is that the diagonals of a rectangle bisect each other and are equal in length. Two line segments that share the same midpoint and have the same length can form the diagonals of a rectangle. By grouping point pairs by their shared midpoint and diagonal length, we can efficiently find candidate rectangles.

Approach

  1. Store all points in a set for O(1) lookup.
  2. Group pairs by midpoint and distance: For every pair of points (p1, p2), compute the midpoint and the squared distance between them. Group pairs that share the same midpoint and the same distance together — these pairs could be diagonals of the same rectangle.
  3. Check candidate rectangles: For each group of pairs sharing a midpoint and diagonal length, check every combination of two pairs. The four endpoints of two such diagonals form a rectangle. Compute the area of that rectangle.
  4. Track the minimum area across all valid rectangles.
  5. The area of a rectangle given diagonal endpoints (p1, p2) and (p3, p4) where (p1, p2) and (p3, p4) are the two diagonals can be computed as the cross product of two adjacent sides.

Pseudocode

function minimumAreaRectangle(points):
    pointSet = set of all points
    n = len(points)
    minArea = infinity

    # Group by (midpoint, squared diagonal length)
    groups = defaultdict(list)
    for i from 0 to n - 2:
        for j from i + 1 to n - 1:
            p1, p2 = points[i], points[j]
            midX = (p1.x + p2.x) / 2.0
            midY = (p1.y + p2.y) / 2.0
            distSq = (p1.x - p2.x)^2 + (p1.y - p2.y)^2
            key = (midX, midY, distSq)
            groups[key].append((i, j))

    for key, pairs in groups:
        for a from 0 to len(pairs) - 2:
            for b from a + 1 to len(pairs) - 1:
                p1, p2 = points[pairs[a][0]], points[pairs[a][1]]
                p3, p4 = points[pairs[b][0]], points[pairs[b][1]]
                # p1 and p3 are adjacent corners
                side1 = (p3.x - p1.x, p3.y - p1.y)
                side2 = (p4.x - p1.x, p4.y - p1.y)
                area = abs(side1.x * side2.y - side1.y * side2.x)
                if area > 0:
                    minArea = min(minArea, area)

    return minArea if minArea != infinity else 0

Time & Space Complexity

  • Time: O(n^2) to enumerate all pairs and group them. In the worst case, if many pairs share the same midpoint and diagonal length, checking combinations within a group can approach O(n^2) per group. Overall worst case is O(n^2 + k) where k is the total number of candidate pair combinations.
  • Space: O(n^2) for storing all pair groupings.

Key Insights

  • The diagonals of a rectangle bisect each other and have equal length. This geometric invariant is the foundation of the grouping strategy.
  • By using midpoint + diagonal length as a hash key, we reduce the search space drastically compared to checking all 4-point combinations (O(n^4)).
  • The area of the rectangle formed by adjacent sides can be computed via the cross product, avoiding the need for trigonometry.
  • For the special case of axis-aligned rectangles, a simpler O(n^2) approach exists: for each pair of points sharing neither x nor y coordinate, check if the other two corners exist in the point set.

Edge Cases

  • Fewer than 4 points: no rectangle is possible, return 0.
  • All points are collinear: no rectangle can be formed.
  • Duplicate points: do not form valid rectangles (area would be 0).
  • Very large coordinates: use appropriate numeric precision for midpoint and distance calculations.
  • Multiple rectangles with the same minimum area: return the area value (not the points).
  • Degenerate "rectangles" with zero area (three or more collinear points forming a diagonal): filtered out by the area > 0 check.

Linked mentions