Problem Breakdown
We are given a list of distinct 2D coordinates representing points on an xy-plane. The goal is to find the smallest area among all possible rectangles that can be formed using these points as corners, provided their sides must remain parallel to the x and y axes (axis-aligned). If no such rectangle exists—meaning we cannot form four right angles with existing points—we return 0.
Inputs: A list of lists points, where each inner list contains two integers [x, y].
Outputs: An integer representing the minimum area found, or 0 if none exist.
Constraints & Edge Cases:
- Points are distinct (no duplicates).
- Coordinates can be up to 40,000.
- Number of points is small (), but large enough that solutions might TLE in stricter environments or if constraints were higher.
- We must handle cases where fewer than 4 points exist (impossible to form a rectangle) and cases where no valid diagonal pairs can be formed from the input set.
Intuition
A naive brute-force approach would iterate through every triplet of points, checking for right angles using slopes or dot products. This is because we pick 3 points out of N to check if they form a corner and then search for the fourth point ( with hashing). Even optimizing that lookup doesn’t help much since finding valid corners requires verifying existence of specific coordinates.
The key insight here relies on the definition of an axis-aligned rectangle: it is defined by two opposite diagonal points and . If these exist in our set, we only need to verify that the other two corners— and —also exist.
This reduces the problem significantly:
- Brute Force: Iterate all pairs of points as potential diagonals (). For each pair, check if other two corners exist in a linear scan or hash set. With an lookup structure (Hash Set), this becomes efficient enough for N=500.
- Optimization: By storing all points in a Hash Set (
setin Python) upfront, we can perform existence checks in constant time on average. We iterate through every unique pair of points and treat them as potential diagonals only if they share neither x nor y coordinates (otherwise they are collinear).
Approach
- Preprocessing: Convert the input list into a
setfor lookup time. This allows us to check “does point exist?” instantly. - Initialization: Initialize
min_areato infinity (or a sufficiently large number). A flag or sentinel value helps distinguish between “found” and “not found”. - Iteration: Use nested loops to iterate through all unique pairs of points from the input list:
- Outer loop index goes from to .
- Inner loop index goes from to .
- Validation: For each pair with coordinates and :
- Check if they can form a diagonal of an axis-aligned rectangle (i.e., AND ). If they share an X or Y coordinate, they lie on the same vertical/horizontal line and cannot be opposite corners.
- Check if points and exist in our set using
inoperator.
- Update: If both missing corner points exist:
- Calculate width and height .
- Area width height.
- Update
min_areaif current area is smaller than the stored minimum.
- Return: If no rectangle was found (area remains infinity), return 0; otherwise, return
min_area.
Complexity Analysis
- Time Complexity: . We iterate through all unique pairs of points once (). Inside the loop, set lookups are average case and arithmetic operations are constant time. Thus, total complexity is dominated by the nested loops: .
- Note: Given constraints (), this results in roughly 125,000 iterations max, which easily fits within time limits. For larger , coordinate-based hashing (bucket sort style) could be considered if coordinates were dense and small enough to fit a grid map without memory overhead exceeding the point set size.
- Space Complexity: to store the points in a hash set for constant-time lookups.
Solution
class Solution:
def minAreaRect(self, points):
# Convert list of lists into a set of tuples for O(1) lookup time
point_set = {tuple(p) for p in points}
min_area = float('inf')
n = len(points)
# Iterate through all unique pairs to treat 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 they can form a diagonal (must not share X or Y)
if x1 == x2 or y1 == y2:
continue
# Verify the other two corners exist in our set
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)
# Return 0 if no rectangle was found, otherwise return minimum area
return 0 if min_area == float('inf') else int(min_area)
Edge Cases Handled
- No Rectangle Possible: If the loop finishes without finding valid corners (e.g., points are collinear or insufficient to form a box),
min_arearemains infinity, and we correctly return 0. - Collinear Points: The condition
if x1 == x2 or y1 == y2: continueensures that pairs lying on the same vertical or horizontal line do not trigger area calculations (as they cannot be opposite corners of an axis-aligned rectangle). - Small Input Size: If fewer than 4 points exist, the nested loops either don’t execute enough times to find a valid pair with distinct coordinates and existing neighbors, naturally resulting in returning 0.