You are given an array of points in the X-Y plane points where points[i] = [xi, yi].
Return the minimum area of a rectangle formed from these points, with sides parallel to the X and Y axes. If there is not any such rectangle, return 0.
Example 1:
Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]] Output: 4
Example 2:
Input: points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]] Output: 2
Constraints:
1 <= points.length <= 500points[i].length == 20 <= xi, yi <= 4 * 104The #939 Minimum Area Rectangle problem asks you to find the smallest axis-aligned rectangle that can be formed from a set of 2D points. A rectangle is valid only if all four of its corners exist in the input.
A common strategy uses a hash-based lookup. Store all points in a HashSet so that coordinate existence checks are constant time. Then treat every pair of points as potential diagonal corners. If the x-coordinates and y-coordinates differ, they can form a rectangle. The other two required corners can be verified using the hash set.
Another efficient idea groups points by x-coordinate and tracks pairs of y-values seen before. By remembering previously encountered vertical pairs, you can compute rectangle areas whenever the same pair appears again at a new x-position.
Both methods rely on fast membership checks and geometric observation of rectangles. Typical solutions run in around O(n^2) time with O(n) additional space depending on the implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| HashSet diagonal check | O(n^2) | O(n) |
| Column grouping with y-pair tracking | O(n^2) | O(n) |
take U forward
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, sorting points by x-coordinate can help group vertical columns together. By tracking pairs of y-values seen at previous x positions, you can detect rectangles and compute their area efficiently when the same pair appears again.
Yes, this problem or its variations can appear in technical interviews, especially for companies that test geometry and hash-based reasoning. It evaluates your ability to combine coordinate geometry with efficient data structures.
A HashSet or hash map is the most useful data structure for this problem. It allows constant-time checks to see whether a coordinate exists, which is critical when verifying the other two rectangle corners efficiently.
A common optimal strategy stores all points in a hash set and checks pairs of points as possible rectangle diagonals. If the other two corners exist, a rectangle is formed and its area can be computed. This approach usually runs in O(n^2) time with constant-time lookups.