Algorithm
Problem Name: 939. Minimum Area Rectangle
Problem Link: https://leetcode.com/problems/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 <= 500points[i].length == 20 <= 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;
struct e_s *shadow;
} 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;
e->shadow = ht->e[hc];
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;
}
Input
points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output
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;
}
};
Input
points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output
4
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int minAreaRect(int[][] points) {
Map new ArrayList()).add(y);
}
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;
}
}
Input
points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output
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()
xmap[x].add(y)
ymap[y].add(x)
})
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
};
Input
points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output
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
Input
points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output
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;
}
}
}
Input
points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output
4