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.
This approach focuses on the principle that a rectangle can be formed if two points are opposite corners (diagonals), and we can determine the other two corners by checking the perpendicularity of the vectors and equality of distances. For each pair of points, we calculate midpoints and perpendicular vectors to check for potential rectangle formation.
The solution involves iterating over all triplets of points and checking if they can form an angle of 90 degrees between them using the dot product. If a fourth point exists that complements the orthogonal points, we calculate the area using the determinant of the vectors (base * height), and update the minimum area found. If no such rectangle is found, we return 0.
Time Complexity: O(n^3), given the need to explore all combinations of triplets. Space Complexity: O(n), used for storing points in a set.
Another approach to solving the problem is by leveraging the properties of the midpoint and circle concepts. In this method, for each pair of points considered as the diagonal of a rectangle, we calculate the midpoint and use the Euclidean distance to check for the possibility of a rectangle. This relies on being able to derive potential opposite points based on known diagonals and midpoints.
This Java solution captures the key ideas of using midpoints and organizes pairs by identical midpoints and circle radius. When pairs share these properties, they might form valid rectangle diagonals, thus computing the area between parallel sides.
Time Complexity: O(n^2), since pairs of points are detected, and their midpoints and radii are utilized for hashing. Space Complexity: O(n^2), which arises due to storage of midpoints and circle data.
We use a hash table to store all the points, then enumerate three points p_1 = (x_1, y_1), p_2 = (x_2, y_2), p_3 = (x_3, y_3), where p_2 and p_3 are the two endpoints of the diagonal of the rectangle. If the line formed by p_1 and p_2 and the line formed by p_1 and p_3 are perpendicular, and the fourth point (x_4, y_4)=(x_2 - x_1 + x_3, y_2 - y_1 + y_3) exists in the hash table, then we have found a rectangle. At this point, we can calculate the area of the rectangle and update the answer.
Finally, if a rectangle that satisfies the conditions is found, return the minimum area among them. Otherwise, return 0.
The time complexity is O(n^3) and the space complexity is O(n), where n is the length of the array points.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Vector Properties and Diagonals | Time Complexity: O(n^3), given the need to explore all combinations of triplets. Space Complexity: O(n), used for storing points in a set. |
| Circle Properties and Midpoint | Time Complexity: O(n^2), since pairs of points are detected, and their midpoints and radii are utilized for hashing. Space Complexity: O(n^2), which arises due to storage of midpoints and circle data. |
| Hash Table + Enumeration | — |
| 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. |
LeetCode 963. Minimum Area Rectangle II Explanation and Solution • happygirlzt • 4,719 views views
Watch 9 more video solutions →Practice Minimum Area Rectangle II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor