# 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```

We need to count each rectangle by right-most edge.

1. Group the `y` points by `x` coordinates, so that we have columns of points. `<X,[List of Y]>`
2. Then, for every pair of points in a column (with coordinates `(x,y1)` and `(x,y2)`), check for the smallest rectangle with this pair of points as the rightmost edge. We can do this by keeping the memory of what pairs of points we’ve seen before.
```class Solution {
public int minAreaRect(int[][] points) {

if(points.length == 0 || points[0].length == 0){
return 0;
}
Map<Integer, List<Integer>> map = new TreeMap<>();
for(int[] point : points){
int x = point[0];
int y = point[1];
List<Integer> yList = map.get(x);
if(yList == null){
yList = new ArrayList<>();
map.put(x, yList);
}
}
int minArea = Integer.MAX_VALUE;
Map<String, Integer> seenX = new HashMap<>();
for(int x : map.keySet()){
List<Integer> yList = map.get(x);
Collections.sort(yList);
int size = yList.size();
for(int i = 0 ; i < size ; i++){
int y1 = yList.get(i);
for(int j = i+1 ; j < size ; j++){
int y2 = yList.get(j);
String key = y1 +"_" + y2;
if(seenX.containsKey(key)){
int prev_x = seenX.get(key);
minArea = Math.min(minArea, (x-prev_x) * (y2-y1));
}
seenX.put(key, x);
}
}
}
return minArea == Integer.MAX_VALUE ? 0 : minArea;
}
}
```

Complexity Analysis

• Time Complexity: `O(N3)`, where `N` is the length of `points`.
• Space Complexity: `O(N)`.

‘ ​

Categories: Map

Tagged as: , ,