# 939. Minimum Area Rectangle (Medium)

https://leetcode.com/problems/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. `1 <= points.length <= 500`
2. `0 <= points[i][0] <= 40000`
3. `0 <= points[i][1] <= 40000`
4. All points are distinct.

## Solutions

``````class Solution {
public int minAreaRect(int[][] points) {
Map<Integer, Set<Integer>> map = new HashMap<>();
for (int[] p : points) {
if (!map.containsKey(p[0])) {
map.put(p[0], new HashSet<>());
}

}

int min = Integer.MAX_VALUE;

// since four edges are either parallel to x or axis, we can form a rectangle
// with two diagonal points, then the rest 2 points are determined. The followup
// operation is to check out whether both points are present in the set.

// following method adopts a brute-force way
for (int[] p1 : points) {
for (int[] p2 : points) {
// the link line of two points are not parallel to neither x or y axis
if (p1[0] == p2[0] || p1[1] == p2[1]) {
continue;
}

// make sure that other two points also exists in the set
// absence of either will not do
if (!map.get(p1[0]).contains(p2[1]) || !map.get(p2[0]).contains(p1[1])) {
continue;
}

// compute the minimum area and substitute the old one if the new is smaller
int area = Math.abs(p1[0] - p2[0]) * Math.abs(p1[1] - p2[1]);
min = Math.min(min, area);
}
}

return min == Integer.MAX_VALUE ? 0 : min;
}
}
``````