https://leetcode.com/problems/minimum-area-rectangle/

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

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

가능한 사각형의 최소 크기를 구한다.

hash 안에 set을 넣어서 x 좌표는 hash의 key값으로, y좌표는 set으로 관리한다.

왼쪽 아래 모서리를 가지고 (outer for문) 오른쪽 위(inner for문) 모서리를 찾는다.

오른쪽 위 모서리는 왼쪽 아래보다 항상 커야 할 것이기 때문에 조건으로 잡았다.

그리고 난뒤 (1,1) (3,3)을 찾았다면, 사각형을 만들 수 있는 조건이 완성된다.

왼쪽 위 모서리는 (1,1) 에서 x좌표 1을 가져오고 (3,3) 에서 y좌표를 가져온다. (1, 3)

오른쪽 아래 모서리는 (1,1) 에서 y좌표 1을 가져오고 (3,3)에서 x좌표를 가져온다. (3, 1)

(1,3) 과 (3,1) 이 hash key값과, set의 key값으로 존재한다면 사각형이 완성된다.

이를 구해서 최소 값을 return 시켜주면 된다.

class Solution {
public:
	int minAreaRect(vector<vector<int>>& points) {
		std::unordered_map<int, std::unordered_set<int>> umap;
		int min = INT_MAX;
		for (int i = 0; i < points.size(); ++i)
		{
			umap[points[i][0]].emplace(points[i][1]);
		}
		for (int i = 0; i < points.size(); ++i)
		{				
			for (int j = 0; j < points.size(); ++j)
			{			
				if (points[j][0] > points[i][0] && points[j][1] > points[i][1])
				{
					//왼쪽 위 모서리
					int leftupfirst = points[i][0];
					int leftupsecond = points[j][1];
					//오른쪽 아래 모서리
					int rightdownfirst = points[j][0];
					int rightdownsecond = points[i][1];
					if (umap.find(leftupfirst) != umap.end())
					{
						if (umap[leftupfirst].find(leftupsecond) != umap[leftupfirst].end())
						{
							if (umap.find(rightdownfirst) != umap.end())
							{
								if (umap[rightdownfirst].find(rightdownsecond) != umap[rightdownfirst].end())
								{
									int base = points[j][0] - points[i][0];
									int height = points[j][1] - points[i][1];
									min = std::min(min, base * height);
								}
							}
						}
					}
				}
			}
		}
		return min == INT_MAX? 0 : min;
	}
};

time complexity 는 2중 for문으로 O(n^2) 다시 key값을 찾는 시간 O(1)으로 O(n^2) 이다.

space complexity hash에 n의 점을 저장 해야 해서 O(n)이다.