939. Minimum Area Rectangle

Question

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.

Solutions

  • Method 1: HashSet O(n^2) 
    class Solution {
      public int minAreaRect(int[][] points) {
          Set<Integer> set = new HashSet<>();
          int len = points.length;
          int res = Integer.MAX_VALUE;
          for(int i = 0; i < len; i++){
              int[] first = points[i];
              set.add(first[0] * 40001 + first[1]);
              for(int j = i + 1; j < len; j++){
                  int[] second = points[j];
                  set.add(second[0] * 40001 + second[1]);
                  if(first[0] == second[0] || first[1] == second[1]) continue;
                  int find1 = second[0] * 40001 + first[1], find2 = first[0] * 40001 + second[1];
                  if(set.contains(find1) && set.contains(find2)) 
                      res = Math.min(res, Math.abs(first[0] - second[0]) * Math.abs(first[1] - second[1]));
              }
          }
          return res == Integer.MAX_VALUE ? 0: res;
      }
  }
  • Method 2: TreeMap + HashMap 
      class Solution {
      public int minAreaRect(int[][] points) {
          Map<Integer, List<Integer>> map = new TreeMap<>();
          for(int[] point: points){   //O(nlgn)
              int x = point[0], y = point[1];
              List<Integer> ys = map.getOrDefault(x, new ArrayList<>());
              ys.add(y);
              map.put(x, ys);
          }
          Map<Integer, Integer> last = new HashMap<>(); // key is y diff and x is row number
          int res = Integer.MAX_VALUE;
          for(Map.Entry<Integer, List<Integer>> entry : map.entrySet()){  //O(n)
              List<Integer> list = entry.getValue();
              Collections.sort(list); // O(lineNum lg lineNum)
              for(int i = 0; i < list.size(); i++){
                  int first = list.get(i);
                  for(int j = i + 1; j < list.size(); j++){
                      int second = list.get(j);
                      int key = first * 40001 + second;
                      if(last.containsKey(key)){
                          res = Math.min(res, Math.abs(first - second) * Math.abs(entry.getKey() - last.get(key)));
                      }
                      last.put(key, entry.getKey());
                  }
              }
          }
          return res == Integer.MAX_VALUE ? 0: res;
      }
  }