## Algorithm

Problem Name: 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:

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

Example 2:

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#define HF 1021

typedef struct e_s {
int y1;
int y2;
int x;
} e_t;

typedef struct {
e_t *e[HF];
e_t buff[250000];
int n;
} h_t;

int hash_code(int y1, int y2) {
int hc = y1 * 33 + y2;
return hc % HF;
}

e_t *lookup(h_t *ht, int y1, int y2) {
int hc = hash_code(y1, y2);
e_t *e = ht->e[hc];
while (e && (e->y1 != y1 || e->y2 != y2)) e = e->shadow;
return e;
}

void insert(h_t *ht, int y1, int y2, int x) {
e_t *e = &ht->buff[ht->n ++];
int hc = hash_code(y1, y2);
e->y1 = y1;
e->y2 = y2;
e->x = x;
ht->e[hc] = e;
}

int cmp(const void *a, const void *b) {
int *p1 = *(int **)a;
int *p2 = *(int **)b;

if (p1[0]  <  p2[0]) return -1;
if (p1[0] > p2[0]) return 1;
if (p1[1]  <  p2[1]) return -1;
return 1;
}

int minAreaRect(int** points, int pointsSize, int* pointsColSize){
int i, j, x, y1, y2, area, ans = 0;
e_t *e;
h_t ht = { 0 };

// x ascending, y ascending
qsort(points, pointsSize, sizeof(int *), cmp);

for (int i = 0; i  <  pointsSize - 1; i ++) {
x  = points[i][0];
y1 = points[i][1];
for (j = i + 1; j  <  pointsSize && points[j][0] == x; j ++) {
y2 = points[j][1];
e = lookup(&ht, y1, y2);
if (e) {
area = (x - e->x) * (y2 - y1);
if (ans == 0 || ans > area) ans = area;
e->x = x;
} else {
insert(&ht, y1, y2, x);
}
}
}

return ans;
}
``````
Copy The Code &

Input

cmd
points = [[1,1],[1,3],[3,1],[3,3],[2,2]]

Output

cmd
4

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int minAreaRect(vector<vector<int>>& points) {
int minArea = 0;
set < pair<int, int>>s;
for (auto& p: points) {
s.insert({p[0], p[1]});
}

for (int i = 0; i  <  points.size(); ++i) {
for (int j = 0; j  <  points.size(); ++j) {
auto a = points[i];
auto b = points[j];

if (a[0] == b[0] || a[1] == b[1]) {
continue;
}

pair < int, int> c = {b[0], a[1]};
pair<int, int> d = {a[0], b[1]};

if (s.count(c) && s.count(d)) {
int area = abs(a[1] - b[1]) * abs(b[0] - a[0]);
minArea = minArea ? min(minArea, area) : area;
}
}
}
return minArea;
}
};
``````
Copy The Code &

Input

cmd
points = [[1,1],[1,3],[3,1],[3,3],[2,2]]

Output

cmd
4

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int minAreaRect(int[][] points) {
}
int ans = Integer.MAX_VALUE;
Map < String, Integer> lastX = new HashMap();
for (int x: rows.keySet()) {
List row = rows.get(x);
Collections.sort(row);
for (int i = 0; i  <  row.size(); ++i) {
for (int j = i + 1; j  <  row.size(); ++j) {
int y1 = row.get(i);
int y2 = row.get(j);
String code = y1 + ":" + y2;
if (lastX.containsKey(code)) {
ans = Math.min(ans, (x - lastX.get(code)) * (y2 - y1));
}
lastX.put(code, x);
}
}
}
return ans  <  Integer.MAX_VALUE ? ans : 0;
}
}
``````
Copy The Code &

Input

cmd
points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]

Output

cmd
2

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const minAreaRect = function(points) {
const xmap = {}, ymap = {}
points.forEach(e => {
const [x, y] = e
if(!xmap.hasOwnProperty(x)) xmap[x] = new Set()
if(!ymap.hasOwnProperty(y)) ymap[y] = new Set()
})
let res = Infinity
for(let i = 0, len = points.length; i < len - 1; i++) {
const [x, y] = points[i]
for(let j = i + 1; j  <  len; j++) {
const [x1, y1] = points[j]
if(x === x1 || y === y1) continue
let area = Infinity
if(xmap[x].has(y1) && ymap[y].has(x1)) area = Math.abs(x - x1) * Math.abs(y - y1)
else continue
res = Math.min(res, area>
}
}
return res === Infinity ? 0 : res
};
``````
Copy The Code &

Input

cmd
points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]

Output

cmd
2

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def minAreaRect(self, points):
seen, bases, baseX, res = collections.defaultdict(dict), [], -1, float("inf")
for x, y in sorted(points):
if x != baseX:
baseX, bases = x, []
for base in bases:
if y in seen[base]:
res = min(res, (x - seen[base][y]) * (y - base))
seen[base][y] = x
bases.append(y)
return res if res < float("inf") else 0
``````
Copy The Code &

Input

cmd
points = [[1,1],[1,3],[3,1],[3,3],[2,2]]

Output

cmd
4

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _0939_MinimumAreaRectangle
{
public int MinAreaRect(int[][] points)
{
var pointSet = new HashSet < int>();
foreach (var point in points)
pointSet.Add(40001 * point[0] + point[1]);

var result = int.MaxValue;
for (int i = 0; i  <  points.Length; i++)
for (int j = i + 1; j  <  points.Length; j++)
if (points[i][0] != points[j][0] && points[i][1] != points[j][1])
if (pointSet.Contains(40001 * points[i][0] + points[j][1]) && pointSet.Contains(40001 * points[j][0] + points[i][1]))
result = Math.Min(result, Math.Abs(points[i][0] - points[j][0]) * Math.Abs(points[i][1] - points[j][1]));

return result  <  int.MaxValue ? result : 0;
}
}
}
``````
Copy The Code &

Input

cmd
points = [[1,1],[1,3],[3,1],[3,3],[2,2]]

Output

cmd
4