Problem statement

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

Solution 1

There is O(n^3) approach, where we check all triples of points.

Complexity

Time complexity is O(n^3), space complexity is O(1).

Code

class Solution:
    def minAreaFreeRect(self, points):
        ans = float("inf")
        p_set = set((x, y) for x, y in points)
        for (x1, y1), (x2, y2), (x3, y3) in permutations(points, 3):
            x = x1 + x2 - x3
            y = y1 + y2 - y3
            if (x, y) in p_set and (x3-x1)*(x3-x2) + (y3-y1)*(y3-y2) == 0:
                ans = min(ans, abs((x3-x1)*(y3-y2) - (x3-x2)*(y3-y1)))
        
        return ans if ans != float("inf") else 0

Solution 2

There is better approach: the idea is to keep dictionary with key: midpoint of diagonal, length, which uniquely define rectangle. It can be proven that there can be no more than O(n^2) rectangles, when all points lie on one circle with center of symmetry.

Complexity

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

Code

class Solution:
    def minAreaFreeRect(self, P):
        d = defaultdict(list)
        for (x1, y1), (x2, y2) in combinations(P, 2):
            d[x1 + x2, y1 + y2, (x1-x2)**2 + (y1-y2)**2].append((x1, y1))
            
        ans = float("inf")
        for mx, my, dd in d.keys():
            for (x1, y1), (x2, y2) in combinations(d[mx, my, dd], 2):
                x3, y3 = mx - x1, my - y1
                ans = min(ans, abs((x3-x1)*(y3-y2) - (x3-x2)*(y3-y1)))
        
        return ans if ans != float("inf") else 0