Minimum Area Rectangle II
Problem Description
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 <= 50
- points[i].length == 2
- 0 <= xi, yi <= 4 * 104
- All the given points are unique.
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
In the brute force approach, the main idea is to check every combination of four points to see if they can form a rectangle. A rectangle is formed if opposite sides are parallel and equal, and diagonals are equal. Given that there are no additional constraints provided apart from the minimum area requirement, we check all combinations.
The logic involves:
- Iterating through each combination of four points.
- Calculating distances and checking the conditions for being a rectangle.
- Updating the minimum area if a rectangle is formed.
Code:
- Time Complexity: O(n^4), where n is the number of points. We check every combination of four points.
- Space Complexity: O(1), only constant extra space used.
2. Optimized Approach with Efficient Checking
Intuition:
The brute force method, while straightforward, is inefficient due to its high complexity. To optimize, we leverage mathematical properties of vectors and key observations regarding the diagonals of a rectangle. If two given points can be diagonals of a rectangle, the middle point of the diagonal must be the same for both diagonals.
The steps involve:
- Using a map to group other points based on the middle point of potential diagonals.
- Checking for valid rectangles by verifying vector properties for the diagonals.
Code:
- Time Complexity: O(n^2), because we process each pair of points and use a map to store distances.
- Space Complexity: O(n^2), due to storage in the hash maps for diagonal information.