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).
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; }}Video 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.