LeetCode Solutions
939. Minimum Area Rectangle
Time: $O(n^2)$ Space: $O(n)$
class Solution {
public:
int minAreaRect(vector<vector<int>>& points) {
int ans = INT_MAX;
unordered_map<int, unordered_set<int>> xToYs;
for (const vector<int>& 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<int>& p = points[i];
const vector<int>& 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;
}
};
class Solution {
public int minAreaRect(int[][] points) {
int ans = Integer.MAX_VALUE;
Map<Integer, Set<Integer>> 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;
}
}
class Solution:
def minAreaRect(self, points: List[List[int]]) -> int:
ans = math.inf
xToYs = 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