We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Area Rectangle

Difficulty: Medium

Problem Description

You are given an array of points in the X-Y plane where points[i] = [xi, yi]. Return the minimum area of a rectangle formed from these points, with sides parallel to the X and Y axes. If there is not any such rectangle, return 0.

Key Insights

  • A rectangle can be formed if we can find two pairs of points that share the same x-coordinates and y-coordinates.
  • To determine the area of the rectangle, we need to calculate the width and height using the unique x and y coordinates of the points.
  • Using a set to store points can help in constant-time lookups to check if the diagonal points exist.
  • The algorithm should iterate over pairs of points to identify potential rectangles and compute their areas.

Space and Time Complexity

Time Complexity: O(n^2) - We need to check all pairs of points to find potential rectangles.

Space Complexity: O(n) - We use a set to store points for fast lookup.

Solution

The solution employs a hash set to store the points for quick access. We iterate through all pairs of points and check if the diagonal points exist in the set. If they do, we calculate the area of the rectangle formed and keep track of the minimum area found.

Code Solutions

def minAreaRect(points):
    point_set = set(map(tuple, points))
    min_area = float('inf')
    found = False

    for i in range(len(points)):
        for j in range(i + 1, len(points)):
            x1, y1 = points[i]
            x2, y2 = points[j]
            if x1 != x2 and y1 != y2:  # Check if they can form a rectangle
                if (x1, y2) in point_set and (x2, y1) in point_set:
                    area = abs(x1 - x2) * abs(y1 - y2)
                    min_area = min(min_area, area)
                    found = True

    return min_area if found else 0
← Back to All Questions