Problem

You are given an array of points in the X-Y plane points where points[i] = [xi, yi].

Return the minimum area of any rectangle formed from these points, with sidesnot necessarily parallel to the X and Y axes. If there is not any such rectangle, return 0.

Answers within 10-5 of the actual answer will be accepted.

Examples

Example 1

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2018/12/21/1a.png)

Input: points = [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.

Example 2

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2018/12/22/2.png)

Input: points = [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.

Example 3

1
2
3
4
5
6


![](https://assets.leetcode.com/uploads/2018/12/22/3.png)

Input: points = [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.

Constraints

  • 1 <= points.length <= 50
  • points[i].length == 2
  • 0 <= xi, yi <= 4 * 10^4
  • All the given points are unique.

Solution

Method 1 – Hash Set + Geometry

Intuition

To find the minimum area rectangle (not necessarily axis-aligned), we need to check all quadruples of points that can form a rectangle. For any two points, if their midpoint and distance are the same as another pair, they can be diagonally opposite corners of a rectangle. We use a hash map to group pairs by their midpoint and distance, then check for rectangles.

Approach

  1. For each pair of points, compute their midpoint and squared distance.
  2. Group pairs by (midpoint, distance) in a hash map.
  3. For each group, for every pair of pairs, compute the area using the distance between one pair and the other.
  4. Track the minimum area found.
  5. Return the minimum area, or 0 if no rectangle is found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def min_area_free_rect(points: list[list[int]]) -> float:
    from collections import defaultdict
    import math
    n = len(points)
    mp = defaultdict(list)
    for i in range(n):
        for j in range(i+1, n):
            x1, y1 = points[i]
            x2, y2 = points[j]
            mid = ((x1 + x2) / 2, (y1 + y2) / 2)
            dist = (x1 - x2) ** 2 + (y1 - y2) ** 2
            mp[(mid, dist)].append((i, j))
    ans = float('inf')
    for pairs in mp.values():
        for a in range(len(pairs)):
            for b in range(a+1, len(pairs)):
                i1, j1 = pairs[a]
                i2, j2 = pairs[b]
                p1, p2, p3 = points[i1], points[j1], points[i2]
                d1 = math.hypot(p1[0] - p3[0], p1[1] - p3[1])
                d2 = math.hypot(p2[0] - p3[0], p2[1] - p3[1])
                area = d1 * d2
                if area < ans and area > 1e-8:
                    ans = area
    return 0 if ans == float('inf') else ans

Complexity

  • ⏰ Time complexity: O(n^3)
    • Enumerating all pairs and checking rectangles.
  • 🧺 Space complexity: O(n^2)
    • For storing pairs in the hash map.