Minimum Area Rectangle
MediumHash Set · NVIDIA
You are given an array points of distinct points on the plane, where points[i] = [x, y].
Return the minimum area of a rectangle whose sides are parallel to the x and y axes and whose four corners are all points in points. In other words, pick two different x values x1 < x2 and two different y values y1 < y2 such that all four points [x1, y1], [x1, y2], [x2, y1], [x2, y2] exist; the area is (x2 - x1) * (y2 - y1).
- Other points lying inside or on the edge of a rectangle do not matter.
- Rotated (non axis-aligned) rectangles do not count.
- If no such rectangle exists, return
0.
Example 1
- Input:
- points = [[0, 0], [0, 2], [3, 0], [3, 2], [1, 0], [1, 2], [1, 5]]
- Output:
- 2
- Explanation
- Three rectangles can be closed: x in [0, 1] (area 1 * 2 = 2), x in [1, 3] (area 2 * 2 = 4) and x in [0, 3] (area 3 * 2 = 6). The smallest is 2. The point
[1, 5]is never part of a rectangle.
Example 2
- Input:
- points = [[2, 1], [2, 4], [5, 1], [6, 4], [2, 6], [5, 6]]
- Output:
- 15
- Explanation
[2, 1],[5, 1],[2, 6],[5, 6]form a 3 by 5 rectangle. The pair[2, 4]and[6, 4]would need[2, y]and[6, y]partners at the same height, which do not exist.
Example 3
- Input:
- points = [[1, 1], [2, 2], [1, 3], [3, 1]]
- Output:
- 0
- Explanation
- No choice of two x values and two y values has all four corner points present, so no rectangle exists.
Constraints
1 <= points.length <= 500points[i].length == 20 <= x, y <= 4 * 10^4- All points are distinct