# 939. Minimum Area Rectangle

• Time: $O(n^2)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: int minAreaRect(vector>& points) { int ans = INT_MAX; unordered_map> xToYs; for (const vector& p : points) xToYs[p[0]].insert(p[1]); for (int i = 1; i < points.size(); ++i) for (int j = 0; j < i; ++j) { const vector& p = points[i]; const vector& q = points[j]; if (p[0] == q[0] || p[1] == q[1]) continue; if (xToYs[p[0]].count(q[1]) && xToYs[q[0]].count(p[1])) ans = min(ans, abs(p[0] - q[0]) * abs(p[1] - q[1])); } return ans == INT_MAX ? 0 : ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int minAreaRect(int[][] points) { int ans = Integer.MAX_VALUE; Map> xToYs = new HashMap<>(); for (int[] p : points) { xToYs.putIfAbsent(p[0], new HashSet<>()); xToYs.get(p[0]).add(p[1]); } for (int i = 1; i < points.length; ++i) for (int j = 0; j < i; ++j) { int[] p = points[i]; int[] q = points[j]; if (p[0] == q[0] || p[1] == q[1]) continue; if (xToYs.get(p[0]).contains(q[1]) && xToYs.get(q[0]).contains(p[1])) ans = Math.min(ans, Math.abs(p[0] - q[0]) * Math.abs(p[1] - q[1])); } return ans == Integer.MAX_VALUE ? 0 : ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def minAreaRect(self, points: List[List[int]]) -> int: ans = math.inf xToYs = collections.defaultdict(set) for x, y in points: xToYs[x].add(y) for i in range(len(points)): for j in range(i): x1, y1 = points[i] x2, y2 = points[j] if x1 == x2 or y1 == y2: continue if y2 in xToYs[x1] and y1 in xToYs[x2]: ans = min(ans, abs(x1 - x2) * abs(y1 - y2)) return ans if ans < math.inf else 0