Problem description:

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

1
2
Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

Example 2:

1
2
Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2

Note:

1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        int minarea= INT_MAX;
        set<pair<int, int>> pointSet;
        for(auto point: points)
            pointSet.insert(make_pair(point[0], point[1]));
        
        for(int i= 0; i< points.size()-1; i++){
            for(int j= i+1; j< points.size(); j++){
                //points[i]
                //points[j]
                int x1= points[i][0], y1= points[i][1];
                int x2= points[j][0], y2= points[j][1];
                
                if(x1!=x2 && y1!=y2 && x1!=y2 && x2!=y1)
                    if(pointSet.count({x1, y2}) && pointSet.count({x2, y1})){
                        minarea= min(minarea, abs((x2-x1)*(y2-y1)));
                    }
            }
        }
        return minarea == INT_MAX? 0: minarea;
    }
};

time complexity: $O(n^2)$
space complexity: $O(n)$
reference: