Minimum Area Rectangle II Solution in Python

Explore More Solutions

Ah, the Minimum Area Rectangle II problem on LeetCode! It’s like trying to find the smallest parking spot in a crowded lot, but instead of cars, you have points on a plane. You’re tasked with finding the minimum area of a rectangle that can be formed by four points, but here’s the kicker: the rectangle can be tilted! So, if you thought finding a parking spot was tough, try doing it while spinning in circles!

Imagine you’re at a party, and you want to find the smallest dance floor that can fit four of your friends who are all standing at different angles. You can’t just shove them into a square; you need to find the perfect rectangle that fits them just right. That’s the essence of this problem!

Code Solution


import math
import collections

class Solution:
    def minAreaFreeRect(self, points: list[list[int]]) -> float:
        ans = math.inf
        centerToPoints = collections.defaultdict(list)

        for ax, ay in points:
            for bx, by in points:
                center = ((ax + bx) / 2, (ay + by) / 2)
                centerToPoints[center].append((ax, ay, bx, by))

        def dist(px: int, py: int, qx: int, qy: int) -> float:
            return (px - qx)**2 + (py - qy)**2

        for points in centerToPoints.values():
            for ax, ay, _, _ in points:
                for cx, cy, dx, dy in points:
                    if (cx - ax) * (dx - ax) + (cy - ay) * (dy - ay) == 0:
                        squaredArea = dist(ax, ay, cx, cy) * dist(ax, ay, dx, dy)
                        if squaredArea > 0:
                            ans = min(ans, squaredArea)

        return 0 if ans == math.inf else math.sqrt(ans)

Approach Explanation

The code works by first calculating the midpoints of all pairs of points and storing them in a dictionary. For each unique midpoint, it checks pairs of points that share that midpoint to see if they can form a rectangle. The key condition is that the vectors formed by the points must be perpendicular to each other. If they are, it calculates the area and keeps track of the minimum area found.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n²)
Space Complexity	O(n)

Real-World Example

Imagine you’re an architect trying to design a new park. You have a bunch of trees (points) scattered around, and you want to create a rectangular picnic area that can fit the maximum number of people while avoiding the trees. This problem is akin to finding that perfect rectangle that allows for maximum enjoyment without disturbing the trees!