Skip to content

939. Minimum Area Rectangle

Difficulty Topics

Description

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.

Solution

minimum-area-rectangle.py
class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        n = len(points)
        p = defaultdict(set) 
        res = float('inf')

        for x, y in points:
            p[x].add(y)

        for i in range(n):
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                if x1 == x2 or y1 == y2: continue

                # x3, y3 = x1, y2
                # x4, y4 = x2, y1

                if y2 in p[x1] and y1 in p[x2]:
                    area = abs(x2 - x1) * abs(y1 - y2)
                    res = min(res, area)

        return 0 if res == float('inf') else res