DSA problem
Minimum Area Rectangle
You are given an array of points in the X-Y plane, where each point is represented as [x_i, y_i]. Return the minimum area of any rectangle that can be formed from these points such that the sides of the rectangle are parallel to the X and Y axes. If there is no such rectangle, return 0.
Axis-aligned rectangles have a very specific structure: their four corners are exactly (x1, y1), (x1, y2), (x2, y1), (x2, y2) for some pair of distinct x-coordinates and distinct y-coordinates. So instead of considering arbitrary quadruples, we can iterate over pairs of points that act as one diagonal (x1 < x2 and y1 < y2 or y1 > y2) and check whether the other two corners exist in the point set.
To support fast lookups, store the points in a hash set keyed by the string "x,y" (or any other hashable representation of a point). Then for every pair of points p1, p2 with different x and different y coordinates, check whether (p1.x, p2.y) and (p2.x, p1.y) are also in the set. If both are present, compute the rectangle's area |x1 - x2| * |y1 - y2| and update the running minimum.
The pair iteration is O(n^2) and each lookup is O(1) amortized, giving overall O(n^2) time and O(n) extra space for the hash set. Return 0 if no axis-aligned rectangle was found.
Examples
points = [[1,1],[1,3],[3,1],[3,3],[2,2]]4points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]2points = [[1,1],[2,2],[3,3]]0Constraints
- 1 <= points.length <= 500
- points[i].length == 2
- 0 <= x_i, y_i <= 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.