# Minimum Area Rectangle II **Difficulty:** MEDIUM [External](https://leetcode.com/problems/minimum-area-rectangle-ii) Canonical: https://scaleengineer.com/dsa/problems/minimum-area-rectangle-ii **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry) **Data structures:** Array **Companies:** [Verily](https://scaleengineer.com/companies/verily) --- ## 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 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:** ![](https://assets.glich.co/dsa/minimum-area-rectangle-ii/image0.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:** ![](https://assets.glich.co/dsa/minimum-area-rectangle-ii/image1.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:** ![](https://assets.glich.co/dsa/minimum-area-rectangle-ii/image2.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 * 104` * All the given points are **unique**. # Approaches ## Brute-Force by Checking All Quartets 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. **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. **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). ### Explanation 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. ### Algorithm * Initialize `minArea` to a very large value. * Generate all combinations of 4 points from the input array `points` using 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: 1. **Same Midpoint**: `(p1.x + p3.x) == (p2.x + p4.x)` and `(p1.y + p3.y) == (p2.y + p4.y)`. 2. **Same Length**: `distanceSq(p1, p3) == distanceSq(p2, p4)`. * 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 update `minArea`. * After checking all combinations, if `minArea` is still the initial large value, return 0. Otherwise, return `minArea`. ## Iterating Through Triplets to Find the Fourth Point 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. **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. **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. ### Explanation 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. ```java 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 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)); } } ``` ### Algorithm * Pre-process all input points into a `HashSet` for efficient `O(1)` average time lookups. To store a point `[x, y]`, we can use a unique key like a string `x + "," + y`. * Initialize `minArea` to a very large value. * Iterate through all unique combinations of three points `p1`, `p2`, and `p3` using 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 vectors `p1->p2` and `p1->p3` are perpendicular using the dot product: `(x2-x1)*(x3-x1) + (y2-y1)*(y3-y1) == 0`. * If they are perpendicular, the fourth point `p4` that completes the rectangle is determined by vector addition: `p4 = p2 + p3 - p1`. * Check if the calculated point `p4` exists in the `HashSet`. * If `p4` exists, a rectangle is found. Calculate its area: `distance(p1, p2) * distance(p1, p3)`. Update `minArea` with this new area if it's smaller. * Repeat this check for right angles at `p2` and `p3`. * After checking all triplets, return `minArea` if it was updated, otherwise return 0. ## Grouping by Diagonal Center and Length 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. **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. **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. ### Explanation 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. ```java 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> 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 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)); } } ``` ### Algorithm * Create a `Map` where 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 use `2 * center` coordinates to avoid floating-point numbers in the key. * Value: `List` of points. * Iterate through all pairs of points `(p_i, p_j)` with `i < 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_i` to the list in the map. This step takes `O(N^2)`. * Initialize `minArea` to a very large value. * Iterate through each list of points in the map's values. For each list `L`: * If `L` has fewer than two points, no rectangle can be formed from this group. Continue. * Any two points `p_a` and `p_b` from this list `L` can form a rectangle with their diagonal partners `p_a'` and `p_b'`. The vertices are `p_a, p_b, p_a', p_b'`. The sides are `p_a p_b` and `p_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 list `L` (`O(m^2)` where `m` is list size). * For each pair, calculate the area `distance(p_a, p_b) * distance(p_b, p_a')` and update `minArea`. * Return `minArea` if updated, otherwise 0. # Solutions ### Java ```java class Solution { public double minAreaFreeRect(int[][] points) { int n = points.length; Set 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; } } ``` ### CPP ```cpp 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 ; } }; ``` ### Python ```python 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 ans ```