DSA problem
Minimum Area Rectangle II
You are given an array of points in the XY-plane, points[i] = [xi, yi]. Return the minimum area of any rectangle formed by these points, with sides not necessarily parallel to the axes. If there is no such rectangle, return 0. Answers within 10^-5 of the actual answer are accepted.
This is the "rotated rectangle" generalization of the axis-aligned variant. Without the axis-aligned constraint we cannot fix pairs of x- and y-coordinates; we instead need a geometric characterization of when four points form a rectangle in any orientation.
The key insight is the diagonal property: a quadrilateral is a rectangle iff its two diagonals (a) bisect each other (share a midpoint) and (b) have equal length. We can therefore enumerate all unordered pairs (p_i, p_j) that could serve as one diagonal, group them by their (midpoint, squared length) key, and within each group any two pairs together form a rectangle.
For each rectangle so found, compute its area as |p_i p_k| * |p_i p_l| where (p_i, p_j) and (p_k, p_l) are the two diagonals — i.e., the product of the two adjacent side lengths emanating from p_i. Track the minimum area encountered. The midpoint key uses integer doubled coordinates to avoid floating-point hashing; the squared length is also an integer. The algorithm runs in O(n^2) time on average (with hashmap lookup) and O(n^2) space for the group buckets.
Examples
points = [[1,2],[2,1],[1,0],[0,1]]2.00000points = [[0,1],[2,1],[1,1],[1,0],[2,0]]1.00000points = [[0,3],[1,2],[3,1],[1,3],[2,1]]0Constraints
- 1 <= points.length <= 50
- points[i].length == 2
- 0 <= xi, yi <= 4 * 10^4
- All the given points are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.