Minimum Area Rectangle II
MedPrompt
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 sides not 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.
Example 1:
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:
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:
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 <= 50points[i].length == 20 <= xi, yi <= 4 * 104- All the given points are unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through every possible combination of four points from the input list. For each combination, it checks if these four points can form a rectangle. If they do, it calculates the area and updates the minimum area found so far. This is the most straightforward but least efficient method.
Algorithm
- Initialize
minAreato a very large value. - Generate all combinations of 4 points from the input array
pointsusing four nested loops. - For each combination of four points
p1, p2, p3, p4, verify if they form a rectangle. - To verify, we can check the diagonals. A quadrilateral is a rectangle if its diagonals bisect each other and have equal length. There are three ways to pair up the four points into two diagonals:
(p1, p2)and(p3, p4);(p1, p3)and(p2, p4);(p1, p4)and(p2, p3). - For a pairing, say
(p1, p3)and(p2, p4), check two conditions:- Same Midpoint:
(p1.x + p3.x) == (p2.x + p4.x)and(p1.y + p3.y) == (p2.y + p4.y). - Same Length:
distanceSq(p1, p3) == distanceSq(p2, p4).
- Same Midpoint:
- If both conditions are met, a rectangle is found. Calculate its area using the lengths of two adjacent sides (e.g.,
distance(p1, p2) * distance(p1, p4)) and updateminArea. - After checking all combinations, if
minAreais still the initial large value, return 0. Otherwise, returnminArea.
Walkthrough
The core of this method is to exhaustively check all quartets of points. A group of four points forms a rectangle if and only if they can be paired up to form two diagonals that are equal in length and share the same midpoint. We can iterate through all N C 4 combinations of points. For each combination, we check the three possible ways to form two diagonals. If we find a valid rectangle configuration, we compute its area and compare it with the minimum area found so far.
Complexity
Time
O(N^4), where N is the number of points. There are `O(N^4)` combinations of four points, and checking each takes constant time.
Space
O(1), as we only need a few variables to store the points of the current combination and the minimum area.
Trade-offs
Pros
Simple to conceptualize and implement.
Uses minimal extra space.
Cons
Very high time complexity, making it impractical for larger N, although it might pass the given constraints (N<=50).
This approach improves upon the brute-force method by iterating through all combinations of three points. For each triplet, it assumes they form two sides of a rectangle meeting at a right angle. It then calculates the expected position of the fourth point and checks if it exists in the input set.
Algorithm
- Pre-process all input points into a
HashSetfor efficientO(1)average time lookups. To store a point[x, y], we can use a unique key like a stringx + "," + y. - Initialize
minAreato a very large value. - Iterate through all unique combinations of three points
p1,p2, andp3using three nested loops. - For each triplet, consider each point as a potential vertex of a right angle. For example, to check for a right angle at
p1, we verify if the vectorsp1->p2andp1->p3are perpendicular using the dot product:(x2-x1)*(x3-x1) + (y2-y1)*(y3-y1) == 0. - If they are perpendicular, the fourth point
p4that completes the rectangle is determined by vector addition:p4 = p2 + p3 - p1. - Check if the calculated point
p4exists in theHashSet. - If
p4exists, a rectangle is found. Calculate its area:distance(p1, p2) * distance(p1, p3). UpdateminAreawith this new area if it's smaller. - Repeat this check for right angles at
p2andp3. - After checking all triplets, return
minAreaif it was updated, otherwise return 0.
Walkthrough
Instead of picking four points, we pick three. Let the points be p1, p2, and p3. We can test if they form a right angle. For instance, if the angle at p1 is a right angle, the vectors p1p2 and p1p3 must be orthogonal. We can verify this using their dot product. If they are, the fourth vertex p4 of the rectangle would be at p1 + (p2-p1) + (p3-p1) = p2 + p3 - p1. We then just need to check if this point p4 exists in our original set of points. To make this check efficient, we first store all points in a HashSet. We repeat this process by considering p2 and p3 as the corner of the right angle.
import java.util.HashSet;import java.util.Set; class Solution { public double minAreaFreeRect(int[][] points) { int n = points.length; if (n < 4) return 0.0; Set<String> pointSet = new HashSet<>(); for (int[] p : points) { pointSet.add(p[0] + "," + p[1]); } double minArea = Double.MAX_VALUE; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) continue; for (int k = 0; k < n; k++) { if (i == k || j == k) continue; int[] p1 = points[i]; int[] p2 = points[j]; int[] p3 = points[k]; // Check for right angle at p1 if ((p2[0] - p1[0]) * (p3[0] - p1[0]) + (p2[1] - p1[1]) * (p3[1] - p1[1]) == 0) { int x4 = p2[0] + p3[0] - p1[0]; int y4 = p2[1] + p3[1] - p1[1]; if (pointSet.contains(x4 + "," + y4)) { double area = distance(p1, p2) * distance(p1, p3); minArea = Math.min(minArea, area); } } } } } return minArea == Double.MAX_VALUE ? 0.0 : minArea; } private double distance(int[] p1, int[] p2) { return Math.sqrt(Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2)); }}Complexity
Time
O(N^3). Three nested loops iterate through all ordered triplets of points. Inside the loops, operations are constant time on average.
Space
O(N) to store the points in a `HashSet` for quick lookups.
Trade-offs
Pros
Significantly faster than the O(N^4) approach.
Relatively simple logic.
Cons
While better than O(N^4), it may still be too slow for very large datasets, though it's perfectly acceptable for N <= 50.
The most efficient approach relies on a geometric property of rectangles: their diagonals are equal in length and bisect each other (i.e., they share the same midpoint). We can group all pairs of points that could form diagonals by their center and length. If a group contains two or more such diagonals, they can be combined to form rectangles.
Algorithm
- Create a
Mapwhere the key represents a diagonal's properties (center and squared length) and the value is a list of points that are endpoints of such diagonals.- Key: A string like
squared_length + "#" + center_x + "#" + center_y. We use2 * centercoordinates to avoid floating-point numbers in the key. - Value:
List<int[]>of points.
- Key: A string like
- Iterate through all pairs of points
(p_i, p_j)withi < j. For each pair:- Calculate the squared length of the segment
p_i p_j. - Calculate the center of the segment
p_i p_j. - Form the key and add
p_ito the list in the map. This step takesO(N^2).
- Calculate the squared length of the segment
- Initialize
minAreato a very large value. - Iterate through each list of points in the map's values. For each list
L:- If
Lhas fewer than two points, no rectangle can be formed from this group. Continue. - Any two points
p_aandp_bfrom this listLcan form a rectangle with their diagonal partnersp_a'andp_b'. The vertices arep_a, p_b, p_a', p_b'. The sides arep_a p_bandp_a p_b'. - We can find
p_a'using the center:p_a' = 2 * center - p_a. - Iterate through all pairs of points
(p_a, p_b)in the listL(O(m^2)wheremis list size). - For each pair, calculate the area
distance(p_a, p_b) * distance(p_b, p_a')and updateminArea.
- If
- Return
minAreaif updated, otherwise 0.
Walkthrough
We can iterate through all pairs of points (p_i, p_j) and treat them as potential diagonals. For each pair, we calculate its center and squared length. We use a hash map to group pairs that have the same center and length. The key to the map can be a string combining the center coordinates and the squared length, and the value can be a list of points that are endpoints of these diagonals.
After populating the map in O(N^2) time, we iterate through its values. If any list contains m >= 2 points, it means we have m diagonals with the same center and length. Any two of these diagonals, say with endpoints p_a and p_b from our list, form a rectangle. The vertices of this rectangle are p_a, p_b, and their respective partners p_a' and p_b'. We can calculate the area and update our minimum. This involves an inner loop over the pairs of points in the list, leading to a sum(m_k C 2) complexity for the second stage.
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map; class Solution { public double minAreaFreeRect(int[][] points) { int n = points.length; if (n < 4) return 0.0; Map<String, List<int[]>> map = new HashMap<>(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int[] p1 = points[i]; int[] p2 = points[j]; long distSq = (long)(p1[0] - p2[0]) * (p1[0] - p2[0]) + (long)(p1[1] - p2[1]) * (p1[1] - p2[1]); int centerX2 = p1[0] + p2[0]; int centerY2 = p1[1] + p2[1]; String key = distSq + "#" + centerX2 + "#" + centerY2; map.computeIfAbsent(key, k -> new ArrayList<>()).add(p1); } } double minArea = Double.MAX_VALUE; for (String key : map.keySet()) { List<int[]> candidates = map.get(key); if (candidates.size() < 2) continue; for (int i = 0; i < candidates.size(); i++) { for (int j = i + 1; j < candidates.size(); j++) { int[] p1 = candidates.get(i); int[] p3 = candidates.get(j); String[] parts = key.split("#"); int centerX2 = Integer.parseInt(parts[1]); int centerY2 = Integer.parseInt(parts[2]); int[] p2 = {centerX2 - p1[0], centerY2 - p1[1]}; double side1 = distance(p1, p3); double side2 = distance(p3, p2); minArea = Math.min(minArea, side1 * side2); } } } return minArea == Double.MAX_VALUE ? 0.0 : minArea; } private double distance(int[] p1, int[] p2) { return Math.sqrt(Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2)); }}Complexity
Time
O(N^2 * M) in the worst case, where `M` is the maximum number of pairs sharing a center and diagonal length. The total complexity is `O(N^2 + sum(m_k^2))` where `m_k` is the size of the list for key `k`. This can be `O(N^4)` in the worst case (e.g., many points on a circle) but performs much better on average, often closer to `O(N^2)`.
Space
O(N^2) to store the map, as there can be up to `O(N^2)` unique diagonals.
Trade-offs
Pros
Most efficient approach in terms of average-case time complexity.
Scales better than the other approaches for larger N.
Cons
More complex to implement correctly.
Uses more space than the O(N^3) approach.
Solutions
Solution
class Solution {public double minAreaFreeRect(int[][] points) { int n = points.length; Set<Integer> s = new HashSet<>(n); for (int[] p : points) { s.add(f(p[0], p[1])); } double ans = Double.MAX_VALUE; for (int i = 0; i < n; ++i) { int x1 = points[i][0], y1 = points[i][1]; for (int j = 0; j < n; ++j) { if (j != i) { int x2 = points[j][0], y2 = points[j][1]; for (int k = j + 1; k < n; ++k) { if (k != i) { int x3 = points[k][0], y3 = points[k][1]; int x4 = x2 - x1 + x3, y4 = y2 - y1 + y3; if (s.contains(f(x4, y4))) { if ((x2 - x1) * (x3 - x1) + (y2 - y1) * (y3 - y1) == 0) { int ww = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); int hh = (x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1); ans = Math.min(ans, Math.sqrt(1L * ww * hh)); } } } } } } } return ans == Double.MAX_VALUE ? 0 : ans; }private int f(int x, int y) { return x * 40001 + y; }}class Solution { public: double minAreaFreeRect ( vector < vector < int >>& points ) { auto f = []( int x , int y ) { return x * 40001 + y ; }; int n = points . size (); unordered_set < int > s ; for ( auto & p : points ) { s . insert ( f ( p [ 0 ], p [ 1 ])); } double ans = 1e20 ; for ( int i = 0 ; i < n ; ++ i ) { int x1 = points [ i ][ 0 ], y1 = points [ i ][ 1 ]; for ( int j = 0 ; j < n ; ++ j ) { if ( j != i ) { int x2 = points [ j ][ 0 ], y2 = points [ j ][ 1 ]; for ( int k = j + 1 ; k < n ; ++ k ) { if ( k != i ) { int x3 = points [ k ][ 0 ], y3 = points [ k ][ 1 ]; int x4 = x2 - x1 + x3 , y4 = y2 - y1 + y3 ; if ( x4 >= 0 && x4 < 40000 && y4 >= 0 && y4 <= 40000 && s . count ( f ( x4 , y4 ))) { if (( x2 - x1 ) * ( x3 - x1 ) + ( y2 - y1 ) * ( y3 - y1 ) == 0 ) { int ww = ( x2 - x1 ) * ( x2 - x1 ) + ( y2 - y1 ) * ( y2 - y1 ); int hh = ( x3 - x1 ) * ( x3 - x1 ) + ( y3 - y1 ) * ( y3 - y1 ); ans = min ( ans , sqrt ( 1LL * ww * hh )); } } } } } } } return ans == 1e20 ? 0 : ans ; } };class Solution: def minAreaFreeRect(self, points: List[List[int]]) -> float: s = {(x, y) for x, y in points} n = len(points) ans = inf for i in range(n): x1, y1 = points[i] for j in range(n): if j != i: x2, y2 = points[j] for k in range(j + 1, n): if k != i: x3, y3 = points[k] x4 = x2 - x1 + x3 y4 = y2 - y1 + y3 if (x4, y4) in s: v21 = (x2 - x1, y2 - y1) v31 = (x3 - x1, y3 - y1) if v21[0] * v31[0] + v21[1] * v31[1] == 0: w = sqrt(v21[0] ** 2 + v21[1] ** 2) h = sqrt(v31[0] ** 2 + v31[1] ** 2) ans = min(ans, w * h) return 0 if ans == inf else ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.