Skip to content

939. Minimum Area Rectangle

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:

img

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

Example 2:

img

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.

Solution:

class Solution {
    public int minAreaRect(int[][] points) {
        Set<String> pointSet = new HashSet<>();

        for (int[] point : points){
            pointSet.add(point[0] + "," + point[1]);
        }

        int minArea = Integer.MAX_VALUE;

        for (int i = 0; i < points.length; i++){
            for (int j = i + 1; j < points.length; j++){
                int x1 = points[i][0];
                int y1 = points[i][1];
                int x2 = points[j][0];
                int y2 = points[j][1];


                if (x1 != x2 && y1 != y2){ // check diagonal pairs
                    if (pointSet.contains(x1 + "," + y2) && pointSet.contains(x2 + "," + y1)){
                        int area = Math.abs(x2 - x1) * Math.abs(y2 - y1);

                        minArea = Math.min(minArea, area);
                    }
                }
            }
        }

        if (minArea == Integer.MAX_VALUE){
            return 0;
        }else{
            return minArea;
        }
    }
}
// TC: O(n^2)
// SC: O(n)