939. Minimum Area Rectangle

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:

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

Example 2:

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

Note:

1. 1 <= points.length <= 500

2. 0 <= points[i][0] <= 40000

3. 0 <= points[i][1] <= 40000

4. All points are distinct.

// Hashmap
int minAreaRect(vector<vector<int>>& points) { // time: O(n^2); space: O(n)
    unordered_map<int, unordered_set<int> > mp;
    for (const vector<int>& pt : points) mp[pt[0]].insert(pt[1]);
    int res = numeric_limits<int>::max();
    for (const vector<int>& p1 : points) {
        for (const vector<int>& p2 : points) {
            // Try to find the point on the diagonal
            if (p1[0] == p2[0] || p1[1] == p2[1]) continue;
            // Check if other 2 points are existent in the hashmap
            if (mp[p1[0]].count(p2[1]) && mp[p2[0]].count(p1[1])) {
                res = min(res, (abs(p1[0] - p2[0])) * (abs(p1[1] - p2[1]) ) );
            }
        }
    }
    return res == numeric_limits<int>::max() ? 0 : res;
}

// Hashset
// 2^16 = 65536 > 40000, so 16 bits are used to represent a coordinate
int minAreaRect(vector<vector<int>>& points) { // time: O(n^2); space: O(n)
    unordered_set<int> st;
    for (const vector<int>& pt : points) {
        st.insert((pt[0] << 16) | pt[1]);
    }
    int res = numeric_limits<int>::max();
    const int n = points.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            const vector<int>& p1 = points[i], &p2 = points[j];
            if (p1[0] == p2[0] || p1[1] == p2[1]) continue;
            if (st.count((p1[0] << 16) | p2[1]) && st.count((p2[0] << 16) | p1[1]) ) {
                res = min(res, (abs(p1[0] - p2[0])) * (abs(p1[1] - p2[1]) ) );
            }
        }
    }
    return res == numeric_limits<int>::max() ? 0 : res;
}