[Leetcode] Problem 939 - Minimum Area Rectangle

Posted on | In ,

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

No.1

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

Output: 4

No.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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int minAreaRect(int[][] points) {
    int result = Integer.MAX_VALUE;

    Set<Integer> set = new HashSet<>();
    for (int[] point : points) {
        set.add(point[0] << 16 | point[1]);
    }

    int size = set.size();
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            int x0 = points[i][0];
            int y0 = points[i][1];
            int x1 = points[j][0];
            int y1 = points[j][1];

            if (x0 == x1 || y0 == y1)
                continue;

            if (!set.contains(x0 << 16 | y1) || !set.contains(x1 << 16 | y0))
                continue;
            
            int area = Math.abs(x0 - x1) * Math.abs(y0 - y1);
            result = Math.min(area, result);
        }
    }

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