LeetCode [939] Minimum Area Rectangle

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.

class Solution {
    public int minAreaRect(int[][] points) {
        int ret = Integer.MAX_VALUE;
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int[] p : points){
            int x = p[0], y = p[1];
            map.computeIfAbsent(x, k -> new HashSet<>()).add(y);
        }

        for(int[] p1 : points){
            int x1 = p1[0], y1 = p1[1];
            for(int[] p2 : points){
                int x2 = p2[0], y2 = p2[1];
                if(x1==x2 || y1==y2) continue;//p1 and p2 are on the same line
                if(map.get(x1).contains(y2) && map.get(x2).contains(y1)){
                    int s = Math.abs(x1-x2)*Math.abs(y1-y2);
                    ret = Math.min(ret, s);
                }
            }
        }

        return ret==Integer.MAX_VALUE?0:ret;
    }
}