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 * 104In #963 Minimum Area Rectangle II, rectangles can appear at any rotation, so the typical axis-aligned approach will not work. A useful geometric insight is that the diagonals of a rectangle have the same midpoint and equal length. This property allows us to detect rectangles by analyzing pairs of points as potential diagonals.
Iterate through every pair of points and treat them as a possible diagonal. For each pair, compute its midpoint and squared distance. Store pairs that share the same midpoint and diagonal length in a map. If multiple pairs fall into the same group, they can form rectangles.
For each combination of diagonal pairs in the same group, compute the rectangle area using distances between the corresponding vertices (using sqrt or squared distances). Track the minimum area across all valid rectangles.
This approach leverages geometric properties with pair enumeration, resulting in about O(n^2) pair generation and grouping. Extra storage is needed to track diagonal groups.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Diagonal Grouping using Midpoint and Distance | O(n^2 + k^2) where n is number of points and k is pairs in a group | O(n^2) |
NeetCode
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, geometry-based problems like Minimum Area Rectangle II occasionally appear in FAANG-style interviews. They test spatial reasoning, hash map usage, and the ability to derive geometric insights for efficient solutions.
The optimal approach uses a geometric observation that rectangle diagonals share the same midpoint and length. By grouping point pairs with identical midpoints and distances, we can identify candidate rectangles and compute their areas efficiently.
Rectangles have diagonals that bisect each other and are equal in length. By grouping point pairs with identical midpoints and distances, we can identify pairs that could serve as diagonals of the same rectangle.
A hash map is commonly used to group point pairs by their midpoint and squared diagonal length. This allows efficient lookup of potential rectangle diagonals and helps detect valid rectangle combinations quickly.