Minimum Area Rectangle — Solution in Python, Java & C++
Minimum Area Rectangle solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Area Rectangle is a medium coding problem on arrays, hash table and geometry, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Geometry
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given points on a plane, find the minimum area of a rectangle whose four corners are all among the given points and whose sides are parallel to the axes.
Return 0 if no such rectangle exists.
Example 1
Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4
Explanation: The four corner points form a 2 by 2 square.
Example 2
Input: points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2
Explanation: The columns at x = 3 and x = 4 give a 1 by 2 rectangle.
Example 3
Input: points = [[0,0],[1,1]]
Output: 0
Constraints
1 <= points.length <= 500points[i].length == 20 <= x, y <= 40000All points are distinct.
Hints for Minimum Area Rectangle
Hint 1
An axis-parallel rectangle is determined by two opposite corners with different
xand differenty.Hint 2
Given those two corners, the other two are forced:
(x1, y2)and(x2, y1).Hint 3
So put the points in a set and test every ordered pair of candidate diagonals.
How to solve Minimum Area Rectangle
Pick two points as a diagonal. Their x and y values determine the remaining two corners exactly, so a set membership test decides whether the rectangle exists.
Approach
- Insert every point into a set keyed on its coordinates.
- For each ordered pair
(i, j)withx1 < x2andy1 < y2— which fixes the diagonal's orientation and avoids double counting — check whether(x1, y2)and(x2, y1)are both present. - Track the smallest
(x2 - x1) * (y2 - y1)found; return0if none.
Why it works
Sides parallel to the axes mean a rectangle's corner set is exactly {x1, x2} × {y1, y2}, so any two opposite corners determine the whole shape. Requiring x1 < x2 and y1 < y2 names each rectangle by its bottom-left and top-right corner once.
Complexity
- Time —
O(n²) - Space —
O(n)
Pitfalls
- Allowing
x1 == x2ory1 == y2degenerates the rectangle to a line with zero area. - Encoding the point key as
x * 40001 + yis fine, but a plain concatenation without a separator collides. 0is the sentinel for 'no rectangle', sobestcannot simply start at zero and usemin— guard the first assignment.
Reference solution
Python
from typing import List
def minAreaRect(points: List[List[int]]) -> int:
have = set((x, y) for x, y in points)
best = 0
for x1, y1 in points:
for x2, y2 in points:
if x1 >= x2 or y1 >= y2:
continue
if (x1, y2) in have and (x2, y1) in have:
area = (x2 - x1) * (y2 - y1)
if best == 0 or area < best:
best = area
return bestJava
public static int minAreaRect(int[][] points) {
Set<Long> have = new HashSet<>();
for (int[] p : points) have.add((long) p[0] * 40001L + p[1]);
int best = 0;
for (int[] a : points) {
for (int[] b : points) {
int x1 = a[0], y1 = a[1], x2 = b[0], y2 = b[1];
if (x1 >= x2 || y1 >= y2) continue;
if (!have.contains((long) x1 * 40001L + y2)) continue;
if (!have.contains((long) x2 * 40001L + y1)) continue;
int area = (x2 - x1) * (y2 - y1);
if (best == 0 || area < best) best = area;
}
}
return best;
}C++
int minAreaRect(vector<vector<int>>& points) {
unordered_set<long long> have;
for (auto& p : points) have.insert((long long) p[0] * 40001LL + p[1]);
int best = 0;
for (auto& a : points) {
for (auto& b : points) {
int x1 = a[0], y1 = a[1], x2 = b[0], y2 = b[1];
if (x1 >= x2 || y1 >= y2) continue;
if (!have.count((long long) x1 * 40001LL + y2)) continue;
if (!have.count((long long) x2 * 40001LL + y1)) continue;
int area = (x2 - x1) * (y2 - y1);
if (best == 0 || area < best) best = area;
}
}
return best;
}JavaScript
var minAreaRect = function(points) {
var have = {};
for (var t = 0; t < points.length; t++) have[points[t][0] + ":" + points[t][1]] = true;
var best = 0;
for (var i = 0; i < points.length; i++) {
for (var j = 0; j < points.length; j++) {
var x1 = points[i][0], y1 = points[i][1];
var x2 = points[j][0], y2 = points[j][1];
if (x1 >= x2 || y1 >= y2) continue;
if (have[x1 + ":" + y2] !== true || have[x2 + ":" + y1] !== true) continue;
var area = (x2 - x1) * (y2 - y1);
if (best === 0 || area < best) best = area;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets