Skip to content

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<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]].contains(q[1]) && xToYs[q[0]].contains(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<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;
  }
}

 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