Minimum Area Rectangle
Medium · Math · Array · Hash Table · Math · Geometry · Sorting
Problem
You are given a list of distinct points points[i] = [x, y] on the plane.
Return the smallest area of a rectangle whose four corners are all in points and whose sides are parallel to the x and y axes. If no such rectangle exists, return 0.
Examples
Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]] Output: 4
Only one rectangle: corners at x = 1 and 3, y = 1 and 3, area 4. The point (2, 2) is not a corner.
Input: points = [[0,0],[0,2],[3,0],[3,2],[1,0],[1,2]] Output: 2
The rectangle from x = 0 to x = 1 (height 2) has area 2, smaller than the ones reaching x = 3.
Input: points = [[1,1],[2,2],[3,3]] Output: 0
No four points form an axis-aligned rectangle.
Constraints
- 1 <= len(points) <= 500
- len(points[i]) == 2
- 0 <= x, y <= 4 · 10^4
- All points are distinct
Approaches
- Every pair of columns and rows — time O(X² · Y²), space O(n)
Follow-up
What if the sides did not have to be parallel to the axes? Then group pairs of points by their midpoint and length: two pairs with the same midpoint and the same length are the diagonals of a rectangle. That is the same "fix the diagonal" idea, one dimension richer.
Related problems
Start free on Cariara · Coding problems · System design studio
