Note that the question only asks to find the minimum area of a rectangle having sides parallel to x-axis and y-axis. If we have the two diagonal coordinates, (x1,y1) and (x2,y2) and given that the sides are parallel to x-axis and y-axis, it is easy to identify that the other two coordinates of the rectangle will be (x1,y2) and (x2,y1).
(x1,y2) (x2,y2)
------------------------
| |
| |
------------------------
(x1,y1) (x2,y1)
We will use this to solve the question in O(n^2) time. The approach is to preprocess all the coordinates and for each x coordinate, store the set of corresponding y coordinates in a hash table (x -> {y1, y2, y3..}). Then, for each pair of coordinates, if they form a horizontal line (i.e., parallel to x-axis) or a vertical line (i.e., parallel to y-axis), we ignore them as we are only concerned about the coordinates in a diagonal. Else, the pair of points (x1,y1) and (x2,y2) form a rectangle only if we have the points (x1,y2) and (x2,y1) in the given input. We can check this simply by using the hash table/map we created earlier (y1 should exist in map[x2] and y2 should exist in map[x1]).
int minAreaRect(vector<vector<int>>& points) {
// sanity check
if (points.size()<4)
return 0;
unordered_map<int, unordered_set<int>> map;
for (auto v : points) map[v[0]].insert(v[1]);
int res = INT_MAX;
for (int i=0; i<points.size(); i++) {
for (int j=0; j<i; j++) {
if (points[i][0] == points[j][0] || points[i][1] == points[j][1])
continue;
if (map[points[i][0]].count(points[j][1]) && map[points[j][0]].count(points[i][1]))
res = min(res, abs((points[i][0]-points[j][0])*(points[i][1]-points[j][1])));
}
}
return res == INT_MAX ? 0 : res;
}
Time complexity: O(n^2) Space complexity: O(n)