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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Area Rectangle II

Number: 1003

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array of unique points in the X-Y plane, the task is to determine the minimum area of any rectangle that can be formed using these points as vertices. The rectangle may be rotated, i.e. its sides are not required to be parallel to the X or Y axes. If no rectangle can be formed, return 0. Answers within 10⁻⁵ of the actual value are accepted.

Key Insights

  • A rectangle, even when rotated, has the property that its diagonals have the same midpoint and equal lengths.
  • By iterating over every pair of points (which can be potential diagonal endpoints), we can group pairs by their midpoint (represented in a way to avoid floating point issues) and their squared distance.
  • For each group of pairs sharing the same center and squared distance, any two pairs can potentially form a rectangle.
  • Given two candidate diagonal pairs (p, q) and (r, s) with the same midpoint, the rectangle’s area can be computed by taking one vertex p and calculating: • side1 = distance from p to r
    • side2 = distance from p to s
    • area = side1 * side2, provided that the vectors (r - p) and (s - p) are perpendicular (i.e. their dot product is zero).
  • Iterate through all valid pair combinations and keep track of the minimum area found.

Space and Time Complexity

Time Complexity: O(n² * k²) where n is the number of points and k is the number of pairs in each grouping (in worst-case, overall it is O(n⁴), but since n ≤ 50, it is acceptable). Space Complexity: O(n²) for storing all pairs in the dictionary.

Solution

The solution involves:

  1. Iterating over all pairs of points and computing a key based on the pair’s midpoint (using the sum of coordinates to avoid floating point precision issues) and their squared distance.
  2. Storing these pairs in a hash map (dictionary) keyed by (center, squared distance).
  3. For each list in the dictionary with more than one pair, checking every combination of two pairs:
    • Choose one endpoint from the first pair and check with both endpoints of the second pair to form two vectors.
    • Verify that these two vectors are perpendicular (dot product equals 0). This confirms the points form a rectangle.
    • Compute the area of the rectangle as the product of the lengths of the two vectors.
  4. Return the minimum area among all valid rectangles, or 0 if none exist.

Below are code solutions in multiple languages with detailed line-by-line comments.

Code Solutions

import math
from collections import defaultdict

def minAreaFreeRect(points):
    # Number of points
    n = len(points)
    # Dictionary to group pairs by (center, squared distance)
    diag_groups = defaultdict(list)
    
    # Iterate over each unique pair of points
    for i in range(n):
        for j in range(i + 1, n):
            # Compute the center as the sum of coordinates to avoid fractions
            center = (points[i][0] + points[j][0], points[i][1] + points[j][1])
            # Compute the squared distance between the two points (diagonal length squared)
            dx = points[i][0] - points[j][0]
            dy = points[i][1] - points[j][1]
            dist2 = dx*dx + dy*dy
            # Append the pair (points[i], points[j]) to the corresponding group key
            diag_groups[(center, dist2)].append((points[i], points[j]))
    
    min_area = float('inf')
    # For every group of pairs sharing same center and squared distance, they form potential rectangles
    for pairs in diag_groups.values():
        if len(pairs) < 2:
            continue
        # Compare every combination of two pairs from this group
        m = len(pairs)
        for i in range(m):
            for j in range(i + 1, m):
                p, q = pairs[i]
                r, s = pairs[j]
                # For rectangle, choose p as one vertex.
                # Determine vectors from p to r and p to s.
                vec_pr = (r[0] - p[0], r[1] - p[1])
                vec_ps = (s[0] - p[0], s[1] - p[1])
                # Check perpendicularity: (vec_pr) dot (vec_ps) should be zero.
                if vec_pr[0] * vec_ps[0] + vec_pr[1] * vec_ps[1] != 0:
                    # If not perpendicular, try swapping r and s.
                    vec_pr = (s[0] - p[0], s[1] - p[1])
                    vec_ps = (r[0] - p[0], r[1] - p[1])
                    if vec_pr[0] * vec_ps[0] + vec_pr[1] * vec_ps[1] != 0:
                        continue   # Not perpendicular; skip
                # Compute lengths of the two sides
                side1 = math.sqrt(vec_pr[0]*vec_pr[0] + vec_pr[1]*vec_pr[1])
                side2 = math.sqrt(vec_ps[0]*vec_ps[0] + vec_ps[1]*vec_ps[1])
                area = side1 * side2
                # Update the minimum area if a smaller valid rectangle is found
                if area < min_area:
                    min_area = area
    return 0 if min_area == float('inf') else min_area

# Example usage:
# print(minAreaFreeRect([[1,2],[2,1],[1,0],[0,1]]))
← Back to All Questions