Formatted question description: https://leetcode.ca/all/939.html

939. Minimum Area Rectangle (Medium)

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

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

Example 2:

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

Note:

1. 1 <= points.length <= 500
2. 0 <= points[i][0] <= 40000
3. 0 <= points[i][1] <= 40000
4. All points are distinct.

Solution 1.

// OJ: https://leetcode.com/problems/transpose-matrix/
// Time: O(N^2logN)
//   * each point is visited only once with another point -> O(N^2)
//   * ys2.find(y) -> O(logN)
// Space: O(N)
class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        int ans = INT_MAX;
        unordered_map<int, set<int>> m;
        for (auto &p : points) m[p[0]].insert(p[1]);
        for (auto i = m.begin(); i != m.end(); ++i) {
            auto &ys1 = i->second;
            for (auto j = next(i); j != m.end(); ++j) {
                auto &ys2 = j->second;
                int xDist = abs(i->first - j->first);
                int prevY = INT_MIN;
                int minYDist = INT_MAX;
                for (auto &y : ys1) {
                    if (ys2.find(y) == ys2.end()) continue;
                    if (prevY != INT_MIN) {
                        minYDist = min(minYDist, y - prevY);
                    }
                    prevY = y;
                }
                if (minYDist != INT_MAX) ans = min(ans, xDist * minYDist);
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

Java

• Java
• C++
• Python

• class Solution {
      public int minAreaRect(int[][] points) {
          TreeMap<Integer, List<Integer>> treeMap = new TreeMap<Integer, List<Integer>>();
          for (int[] point : points) {
              int x = point[0], y = point[1];
              List<Integer> list = treeMap.getOrDefault(x, new ArrayList<Integer>());
              list.add(y);
              treeMap.put(x, list);
          }
          int minArea = Integer.MAX_VALUE;
          HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
          Set<Integer> xValuesSet = treeMap.keySet();
          for (int x : xValuesSet) {
              List<Integer> list = treeMap.get(x);
              Collections.sort(list);
              int size = list.size();
              for (int i = 0; i < size; i++) {
                  int y1 = list.get(i);
                  for (int j = i + 1; j < size; j++) {
                      int y2 = list.get(j);
                      String positionKey = Arrays.toString(new int[]{y1, y2});
                      if (hashMap.containsKey(positionKey))
                          minArea = Math.min(minArea, (x - hashMap.get(positionKey)) * (y2 - y1));
                      hashMap.put(positionKey, x);
                  }
              }
          }
          return minArea == Integer.MAX_VALUE ? 0 : minArea;
      }
  }
  

• // OJ: https://leetcode.com/problems/transpose-matrix/
  // Time: O(N^2logN)
  //   * each point is visited only once with another point -> O(N^2)
  //   * ys2.find(y) -> O(logN)
  // Space: O(N)
  class Solution {
  public:
      int minAreaRect(vector<vector<int>>& points) {
          int ans = INT_MAX;
          unordered_map<int, set<int>> m;
          for (auto &p : points) m[p[0]].insert(p[1]);
          for (auto i = m.begin(); i != m.end(); ++i) {
              auto &ys1 = i->second;
              for (auto j = next(i); j != m.end(); ++j) {
                  auto &ys2 = j->second;
                  int xDist = abs(i->first - j->first);
                  int prevY = INT_MIN;
                  int minYDist = INT_MAX;
                  for (auto &y : ys1) {
                      if (ys2.find(y) == ys2.end()) continue;
                      if (prevY != INT_MIN) {
                          minYDist = min(minYDist, y - prevY);
                      }
                      prevY = y;
                  }
                  if (minYDist != INT_MAX) ans = min(ans, xDist * minYDist);
              }
          }
          return ans == INT_MAX ? 0 : ans;
      }
  };
  

• class Solution(object):
      def minAreaRect(self, points):
          """
          :type points: List[List[int]]
          :rtype: int
          """
          points = map(tuple, points)
          points.sort()
          pset = set(points)
          N = len(points)
          res = float('inf')
          for i in range(N - 1):
              p1 = points[i]
              for j in range(i + 1, N):
                  p4 = points[j]
                  if p4[0] == p1[0] or p4[1] == p1[1]:
                      continue
                  p2 = (p1[0], p4[1])
                  p3 = (p4[0], p1[1])
                  if p2 in pset and p3 in pset:
                      res = min(res, abs(p3[0] - p1[0]) * abs(p2[1] - p1[1]))
          return res if res != float("inf") else 0
  

All Problems

All Solutions