939. Minimum Area Rectangle

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 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.


Solution:

The brute-force way is to use four for loops to iterate all four points. For each four points, we can determine whether they can form a rectangular and maintain a minimum size.

If 4 points can form a rectangular, they have to be (x₁, y₁), (x₁, y₂), (x₂, y₁), and (x₂, y₂). We can see x₁ exists twice, x₂ exists twice, y₁ exists twice and y₂ exists twice. We can implement an isValid function with this logic.

The bruce-force approach takes O(n⁴) time, which is not good.

A better solution is we can go through all points in O(n) and maintain a HashMap. For each x, we maintain a Set in the map that contains all existing y corresponding to this x.

After building up the map, we can use two for loops to choose any two points in the input. For each two points (A and B), we first determine if they are diagonal. If they are diagonal, we know these two points have different x and different y.

Then we can use the map to check:
1.  there exists a point which has A's x and B's y
2.  there exists a point which has B's x and A's y
3.  check size

This takes O(1) time.

In this way, we can solve the problem in O(n²) time with an additional space for the map.


Code:

class Solution {
    public int minAreaRect(int[][] points) {
        int res = Integer.MAX_VALUE;
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
        for (int[] point : points) {
            if (!map.containsKey(point[0])) {
                map.put(point[0], new HashSet<>());
            }
            map.get(point[0]).add(point[1]);
        }
        for (int[] pointA : points) {
            for (int[] pointB : points) {
                if (pointA[0] == pointB[0] || pointA[1] == pointB[1]) {
                    continue;
                }
                if (!map.get(pointA[0]).contains(pointB[1]) 
                    || !map.get(pointB[0]).contains(pointA[1])) {
                    continue;
                }
                res = Math.min(res, 
                               Math.abs((pointB[0] - pointA[0]) 
                                        * (pointB[1] - pointA[1])
                                        )
                              );
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}