Question

939. Minimum Area Rectangle

中文文档

Description

You are given an array of points in the X-Y plane points where points[i] = [xi, yi].

Return _the minimum area of a rectangle formed from these points, with sides parallel to the X and Y axes_. If there is not any such rectangle, return 0.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= points.length <= 500
• points[i].length == 2
• 0 <= xi, yi <= 4 * 104
• All the given points are unique.

Solutions

Solution 1

class Solution:
  def minAreaRect(self, points: List[List[int]]) -> int:
    d = defaultdict(list)
    for x, y in points:
      d[x].append(y)
    pos = {}
    ans = inf
    for x in sorted(d):
      ys = d[x]
      ys.sort()
      n = len(ys)
      for i, y1 in enumerate(ys):
        for y2 in ys[i + 1 :]:
          if (y1, y2) in pos:
            ans = min(ans, (x - pos[(y1, y2)]) * (y2 - y1))
          pos[(y1, y2)] = x
    return 0 if ans == inf else ans

class Solution {
  public int minAreaRect(int[][] points) {
    TreeMap<Integer, List<Integer>> d = new TreeMap<>();
    for (var p : points) {
      int x = p[0], y = p[1];
      d.computeIfAbsent(x, k -> new ArrayList<>()).add(y);
    }
    Map<Integer, Integer> pos = new HashMap<>();
    int ans = 1 << 30;
    for (var e : d.entrySet()) {
      int x = e.getKey();
      var ys = e.getValue();
      Collections.sort(ys);
      int n = ys.size();
      for (int i = 0; i < n; ++i) {
        int y1 = ys.get(i);
        for (int j = i + 1; j < n; ++j) {
          int y2 = ys.get(j);
          int p = y1 * 40001 + y2;
          if (pos.containsKey(p)) {
            ans = Math.min(ans, (x - pos.get(p)) * (y2 - y1));
          }
          pos.put(p, x);
        }
      }
    }
    return ans == 1 << 30 ? 0 : ans;
  }
}

class Solution {
public:
  int minAreaRect(vector<vector<int>>& points) {
    map<int, vector<int>> d;
    for (auto& p : points) {
      int x = p[0], y = p[1];
      d[x].emplace_back(y);
    }
    unordered_map<int, int> pos;
    int ans = 1 << 30;
    for (auto& [x, ys] : d) {
      sort(ys.begin(), ys.end());
      int n = ys.size();
      for (int i = 0; i < n; ++i) {
        int y1 = ys[i];
        for (int j = i + 1; j < n; ++j) {
          int y2 = ys[j];
          int p = y1 * 40001 + y2;
          if (pos.count(p)) {
            ans = min(ans, (x - pos[p]) * (y2 - y1));
          }
          pos[p] = x;
        }
      }
    }
    return ans == 1 << 30 ? 0 : ans;
  }
};

func minAreaRect(points [][]int) int {
  d := map[int][]int{}
  xs := []int{}
  for _, p := range points {
    x, y := p[0], p[1]
    d[x] = append(d[x], y)
  }
  for x := range d {
    xs = append(xs, x)
  }
  sort.Ints(xs)
  type pair struct{ x, y int }
  pos := map[pair]int{}
  ans := 1 << 30
  for _, x := range xs {
    ys := d[x]
    sort.Ints(ys)
    for i, y1 := range ys {
      for _, y2 := range ys[i+1:] {
        p := pair{y1, y2}
        if x1, ok := pos[p]; ok {
          ans = min(ans, (x-x1)*(y2-y1))
        }
        pos[p] = x
      }
    }
  }
  if ans == 1<<30 {
    return 0
  }
  return ans
}