How do you solve Minimum Area Rectangle II on LeetCode?

Minimum Area Rectangle II (LeetCode #963) 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: The rectangle can be formed by any four points, not just those aligned with axes.

What is the brute force solution for Minimum Area Rectangle II?

The brute force approach for Minimum Area Rectangle II is Brute Force, with O(n²) time complexity and O(1) space complexity. We can check every combination of four points to see if they can form a rectangle. If they do, we calculate the area and keep track of the minimum area found. The optimal Optimal Solution approach improves this to O(n²).

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

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

What are the interview tips for Minimum Area Rectangle II?

Always clarify the problem requirements and constraints before diving into coding. Think about edge cases, such as points that are too few to form a rectangle. Discuss your thought process and approach with the interviewer to demonstrate your understanding.

What are common mistakes when solving Minimum Area Rectangle II?

Failing to check all combinations of points, leading to missed rectangles. Not considering the possibility of rectangles that are rotated.

#963

Minimum Area Rectangle II

Medium

ArrayHash TableMathGeometryHash 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)

We can use a HashMap to store points for quick lookup, and then iterate through pairs of points to determine if they can form a rectangle. This reduces the number of checks significantly.

⚙️

Algorithm

4 steps

1Step 1: Store all points in a HashSet for O(1) lookup.
2Step 2: Iterate through each pair of points to consider them as potential opposite corners of a rectangle.
3Step 3: Calculate the potential other two corners and check if they exist in the HashSet.
4Step 4: If they exist, calculate the area and update the minimum area found.

solution.py14 lines

1def minAreaRect(points):
2    point_set = set(tuple(point) for point in points)
3    min_area = float('inf')
4    for i in range(len(points)):
5        for j in range(i + 1, len(points)):
6            p1, p2 = points[i], points[j]
7            # Calculate potential other corners
8            p3 = (p1[0], p2[1])
9            p4 = (p2[0], p1[1])
10            if p3 in point_set and p4 in point_set:
11                area = abs(p1[0] - p2[0]) * abs(p1[1] - p2[1])
12                min_area = min(min_area, area)
13    return min_area if min_area != float('inf') else 0
14

ℹ

Complexity note: The time complexity remains O(n²) due to the nested loops, but we gain efficiency through O(1) lookups in the HashSet, making it faster in practice.

1The rectangle can be formed by any four points, not just those aligned with axes.
2Using a HashSet allows for quick lookups to verify potential rectangle corners.

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