For each pair of points we want to consider one as the top-left and the other as the bottom-right. Then, we want to find the other two corners: top-right and bottom-left.
Since left two corners must have smaller x-coordinates than the right two corners, we first sort the points by x-coordinate. This reduces the possible 
Time: 
class Solution:
def minAreaRect(self, points: List[List[int]]) -> int:
point_set = set(tuple(p) for p in points)
points.sort()
min_area = float("inf")
for i in range(len(points)):
top_left = points[i]
for j in range(i+1, len(points)):
bottom_right = points[j]
dx = bottom_right[0] - top_left[0]
if dx <= 0:
continue
dy = top_left[1] - bottom_right[1]
if dy <= 0:
continue
top_right = ( top_left[0]+dx, top_left[1] )
if top_right not in point_set:
continue
bottom_left = (top_left[0], top_left[1]-dy)
if bottom_left not in point_set:
continue
min_area = min( min_area, dx * dy )
return min_area if min_area != float("inf") else 0
unreasonably effective 
Leave a comment