Watch 10 video solutions for Minimum Area Rectangle II, a medium level problem involving Array, Math, Geometry. This walkthrough by happygirlzt has 4,719 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 * 104Problem Overview: You are given a list of 2D points. The task is to find the minimum area rectangle that can be formed using any four of these points as vertices. Unlike the classic axis-aligned version, rectangles here can be rotated at any angle, which makes pure coordinate comparisons insufficient.
Approach 1: Vector Properties and Diagonals (O(n^3) time, O(n^2) space)
A rectangle has two key geometric properties: opposite sides are parallel, and adjacent sides are perpendicular. Pick three points A, B, and C and treat them as potential consecutive vertices. Use vector math to check whether AB is perpendicular to AC using a dot product. If the angle is 90 degrees, compute the fourth point D = B + C - A. Store all points in a hash set for O(1) lookup to verify whether D exists. If it does, compute the rectangle area as |AB| * |AC| and track the minimum. This approach directly uses vector operations from geometry and is easy to reason about during interviews.
Approach 2: Circle Properties and Midpoint (O(n^2 log n) time, O(n^2) space)
Rectangles have equal-length diagonals that share the same midpoint. Iterate through every pair of points and treat them as a potential diagonal. For each pair, compute the midpoint and the squared distance between them. Store pairs in a hash map keyed by (midpoint, diagonal length). Points that share the same key belong to rectangles with the same diagonal. For each group, combine two diagonals to form a rectangle and compute its area using vector cross products. This reduces the search space dramatically because rectangles are detected through shared diagonal properties instead of testing every triple of points. The implementation relies on hashing and pair iteration from array processing and geometric distance calculations from math.
Recommended for interviews: The midpoint + diagonal grouping approach is usually expected in strong solutions. It leverages a geometric invariant (same midpoint and length for diagonals) to reduce the brute-force search from cubic checks to pair grouping. Explaining the vector-based approach first shows geometric understanding, but implementing the diagonal hashing method demonstrates stronger optimization and problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Vector Properties and Diagonals | O(n^3) | O(n^2) | Good for understanding rectangle geometry and verifying perpendicular vectors. |
| Circle Properties and Midpoint Grouping | O(n^2 log n) | O(n^2) | Best general solution. Efficiently detects rectangles using shared midpoint and equal diagonals. |