LeetCode Solutions Blog

Minimum Area Rectangle

Number: 976

Difficulty: Medium

Paid? No

Problem Description

Given an array of unique points in the X-Y plane, return the minimum area of a rectangle that can be formed from these points, with sides parallel to the X and Y axes. If no valid rectangle exists, return 0.

Key Insights

Use a hash set (or equivalent) to store points for O(1) lookup.
Iterate over all pairs of points that could form opposite corners of a rectangle (ensuring they have different x and y values).
For each such pair, check if the other two required points exist.
Keep track of the smallest area found; if no rectangle is detected, return 0.

Space and Time Complexity

Time Complexity: O(n^2) where n is the number of points (each pair is inspected). Space Complexity: O(n) for storing the points in a hash set.

Solution

The solution involves iterating through every pair of points. For each pair with distinct x and y coordinates (potential diagonal corners of a rectangle), check if the other two corners (with swapped y and x values) exist in the set. If they do, calculate the area and update the minimum area if it is smaller than the current minimum. If no valid rectangle is found after checking all pairs, return 0.

Code Solutions

# Python solution with step-by-step comments
class Solution:
    def minAreaRect(self, points: List[List[int]]) -> int:
        # Create a set of tuples for O(1) point lookup
        point_set = {(x, y) for x, y in points}
        n = len(points)
        min_area = float('inf')
        
        # Iterate through each pair of points to consider as potential diagonals
        for i in range(n):
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                # Check if the points are diagonally opposite (distinct x and y)
                if x1 != x2 and y1 != y2:
                    # Check if the other two required corners exist
                    if (x1, y2) in point_set and (x2, y1) in point_set:
                        # Calculate the area of the rectangle
                        area = abs(x2 - x1) * abs(y2 - y1)
                        # Update the minimum area if this rectangle is smaller
                        min_area = min(min_area, area)
        
        # If no rectangle was found, return 0; otherwise, return the minimum area
        return 0 if min_area == float('inf') else min_area