How do you solve Minimum Area Rectangle on LeetCode?

Minimum Area Rectangle (LeetCode #939) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: A rectangle requires opposite corners to be present.

What is the brute force solution for Minimum Area Rectangle?

The brute force approach for Minimum Area Rectangle is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach checks every possible pair of points to see if they can form a rectangle. This is simple but inefficient for larger datasets. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Minimum Area Rectangle?

Minimum Area Rectangle uses the following concepts: Array, Hash Table, Math, Geometry, Sorting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Minimum Area Rectangle?

Clarify the problem requirements and constraints before coding. Think about edge cases, like points that don't form a rectangle. Discuss your thought process aloud to engage the interviewer.

What are common mistakes when solving Minimum Area Rectangle?

Not checking for unique points when forming rectangles. Assuming all pairs can form rectangles without checking corner existence.

#939

Minimum Area Rectangle

Medium

ArrayHash TableMathGeometrySortingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

Using a HashSet allows us to quickly check for the existence of the required rectangle corners, reducing unnecessary checks and improving efficiency.

⚙️

Algorithm

4 steps

1Step 1: Store all points in a HashSet for O(1) lookup time.
2Step 2: Iterate through each pair of points to identify potential rectangle corners.
3Step 3: For each pair, check if the other two corners exist in the HashSet.
4Step 4: Calculate the area if all four corners are found and update the minimum area.

solution.py12 lines

1# Full working Python code
2from itertools import combinations
3
4def minAreaRect(points):
5    point_set = set(map(tuple, points))
6    min_area = float('inf')
7    for (x1, y1), (x2, y2) in combinations(points, 2):
8        if x1 != x2 and y1 != y2:
9            if (x1, y2) in point_set and (x2, y1) in point_set:
10                area = abs(x1 - x2) * abs(y1 - y2)
11                min_area = min(min_area, area)
12    return min_area if min_area != float('inf') else 0

ℹ

Complexity note: The time complexity remains O(n²) because we still check every pair of points. However, the space complexity is O(n) due to the HashSet storing the points for quick lookup.

1A rectangle requires opposite corners to be present.
2Using a HashSet allows for faster existence checks.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.