flykiller.github.io

---

layout: post title: Leetcode 0939. Minimum Area Rectangle tags: [geometry, hash table, math, sort, array] —

Problem statement

https://leetcode.com/problems/minimum-area-rectangle/

Solution

The idea is to look at each pairs of point and check if we can build rectangle with given diagonal.

Complexity

Time complexity is O(n^2), space is O(n).

Code

class Solution:
    def minAreaRect(self, points):
        ans = float("inf")
        p_set = set((x, y) for x, y in points)
        for p1, p2 in combinations(points, 2):
            if p1[0] == p2[0] or p1[1] == p2[1]: continue
            if (p1[0], p2[1]) in p_set and (p2[0], p1[1]) in p_set:
                ans = min(ans, abs((p1[0] - p2[0]) * (p1[1] - p2[1])))
        
        return ans if ans != float("inf") else 0

This site is open source. Improve this page.