Minimum Area Rectangle Problem
Description
LeetCode Problem 939.
You are given an array of points in the X-Y plane points where points[i] = [x_i, y_i].
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:
1
2
Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4
Example 2:
1
2
Input: points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2
Constraints:
- 1 <= points.length <= 500
- points[i].length == 2
- 0 <= x_i, y_i <= 4 * 10^4
- All the given points are unique.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
int minAreaRect(vector<vector<int>>& points) {
int ans = INT_MAX;
unordered_map<int, unordered_set<int>> m;
for (auto p : points) {
m[p[0]].insert(p[1]);
}
/*
A ----------------------------D
|(x1, y1) (x2, y1)|
| |
|(x1, y2) (x2, y2)|
C ----------------------------B
*/
for (int i = 0; i < points.size(); i++) {
for (int j = i+1; j < points.size(); j++) {
int x1 = points[i][0]; // A
int y1 = points[i][1]; // A
int x2 = points[j][0]; // B
int y2 = points[j][1]; //B
if ((x1 != x2) && (y2 != y1)) { // diagonal
if (m[x1].find(y2) != m[x1].end() && m[x2].find(y1) != m[x2].end()) { // C & D
ans = min(ans, (abs(x1-x2) * abs(y1-y2)));
}
}
}
}
return ((ans == INT_MAX) ? 0 : ans);
}
};