Minimum Area Rectangle - Leetcode Solution

Problem:

You are given an array of points in the Cartesian plane. You have to find the minimum area of a rectangle formed by any four points in the given array. If there are no rectangles in the array, return 0.

Solution:

The solution to this problem involves a brute force approach. We compute all possible pairs of points and treat them as diagonal points of a rectangle. Then, we verify if the other two points lie on the same horizontal or vertical line as the diagonal points, and if so, we compute the area of the rectangle and keep track of the minimum area found so far.

First, we create a set of points to remove any duplicates, then sort the points by their x coordinate. We then create a dictionary mapping a point's x coordinate to its index in the sorted point array.

For each pair of points (p1, p2), we compute the two other possible points that complete the rectangle (p3, p4) by checking the sorted x-coordinate dictionary for points with the same x-coordinate as p1 and p2 and with a different y-coordinate. If we find both points, we check if they form a rectangle with p1 and p2 by checking if their y-coordinates match. If they do, we compute the area of the rectangle and update the minimum seen so far.

Here is the Python code implementing this approach:

from typing import List

class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        point_set = set(tuple(point) for point in points)
        sorted_points = sorted(point_set)
        x_to_points = {x: [] for x, _ in sorted_points}
        for i, point in enumerate(sorted_points):
            x, y = point
            x_to_points[x].append(i)
        min_area = float('inf')
        for i, (x1, y1) in enumerate(sorted_points):
            for j in range(i):
                x2, y2 = sorted_points[j]
                if x1 == x2 or y1 == y2:
                    continue
                if (x1, y2) in point_set and (x2, y1) in point_set:
                    k, l = x_to_points[x1], x_to_points[x2]
                    p, q = k.index(i), l.index(j)
                    r, s = k.index(l[q]), l.index(k[p])
                    min_area = min(min_area, abs(x1 - x2) * abs(y1 - y2))
        return min_area if min_area != float('inf') else 0

Time Complexity: O(n^2), where n is the number of points in the input array. Space Complexity: O(n), where n is the number of points in the input array.

1