Minimum Area Rectangle Solutions in C++

/// Source : https://leetcode.com/problems/minimum-area-rectangle/
/// Author : liuyubobobo
/// Time   : 2018-11-10

#include <iostream>
#include <set>
#include <vector>

using namespace std;


/// Using Set to store every point
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {

        set<pair<int, int>> set;
        for(const vector<int>& point: points)
            set.insert(make_pair(point[0], point[1]));

        int min_area = INT_MAX;
        for(int i = 0; i < points.size(); i ++)
            for(int j = i + 1; j < points.size(); j ++){
                pair<int, int> p1 = make_pair(points[i][0], points[j][1]);
                pair<int, int> p2 = make_pair(points[j][0], points[i][1]);
                if(set.count(p1) && set.count(p2) &&
                    points[i][0] != points[j][0] && points[i][1] != points[j][1])
                    min_area = min(min_area,
                                   abs(points[i][0] - points[j][0]) * abs(points[i][1] - points[j][1]));
            }
        return min_area == INT_MAX ? 0 : min_area;
    }
};

int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-area-rectangle/
/// Author : liuyubobobo
/// Time   : 2018-11-11

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;


/// Using HashSet to store every point
/// Using Integer to represent evey point
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

private:
    const int N = 40001;

public:
    int minAreaRect(vector<vector<int>>& points) {

        unordered_set<int> set;
        for(const vector<int>& point: points)
            set.insert(point[0] * N + point[1]);

        int min_area = INT_MAX;
        for(int i = 0; i < points.size(); i ++)
            for(int j = i + 1; j < points.size(); j ++){
                int p1 = points[i][0] * N + points[j][1];
                int p2 = points[j][0] * N + points[i][1];
                if(set.count(p1) && set.count(p2) &&
                   points[i][0] != points[j][0] && points[i][1] != points[j][1])
                    min_area = min(min_area,
                                   abs(points[i][0] - points[j][0]) * abs(points[i][1] - points[j][1]));
            }
        return min_area == INT_MAX ? 0 : min_area;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/minimum-area-rectangle/
/// Author : liuyubobobo
/// Time   : 2018-11-12

#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <vector>

using namespace std;


/// Using TreeMap to store every point in column
/// Using a "code" to record every height of each column
/// Tricky in my opinion :-)
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

private:
    const int N = 40001;

public:
    int minAreaRect(vector<vector<int>>& points) {

        map<int, vector<int>> pts;
        for(const vector<int>& point: points)
            pts[point[0]].push_back(point[1]);

        for(const pair<int, vector<int>>& col: pts)
            sort(pts[col.first].begin(), pts[col.first].end());

        unordered_map<int, int> last; // code -> x
        int min_area = INT_MAX;
        for(const pair<int, vector<int>>& col: pts){

            for(int i = 0; i < col.second.size(); i ++)
                for(int j = i + 1; j < col.second.size(); j ++){
                    int code = col.second[i] * N + col.second[j];
                    if(last.count(code))
                        min_area = min(min_area, (col.first - last[code]) * abs(col.second[i] - col.second[j]));
                    last[code] = col.first;
                }
        }
        return min_area == INT_MAX ? 0 : min_area;
    }
};


int main() {

    return 0;
}