AlgoMaster Logo

Minimum Area Rectangle II

Last Updated: March 28, 2026

medium
3 min read

Understanding the Problem

This problem is a step up from the classic "Minimum Area Rectangle" (LeetCode #939) where rectangles had to be axis-aligned. Here, the rectangle can be rotated at any angle. That changes the problem fundamentally, because we can no longer just look for pairs of points sharing an x-coordinate or y-coordinate.

What makes a rectangle a rectangle? Four points where opposite sides are equal and parallel, and all angles are 90 degrees. In coordinate geometry, this means the diagonals of a rectangle bisect each other (share the same midpoint) and have equal length. That geometric property is the key observation that unlocks the efficient solution.

Key Constraints:

  • 1 <= points.length <= 50 → With n up to 50, even O(n^4) would be at most 6.25 million operations, which is perfectly fine. O(n^3) and O(n^2) approaches are also viable.
  • 0 <= xi, yi <= 4 * 10^4 → Coordinates are non-negative integers. This means we can use them as hash keys without worrying about floating-point issues in point lookups.
  • All points are unique → No need to handle duplicate points.

Approach 1: Brute Force (Check All Triples)

Intuition

The most natural approach: pick any three points and figure out where the fourth point of the rectangle would need to be. If that fourth point exists in our set, we have a valid rectangle.

If we pick three points A, B, C and assume A is the corner with the right angle, then vectors AB and AC must be perpendicular. We can check perpendicularity with the dot product: if AB dot AC = 0, the angle at A is 90 degrees. The fourth point D is then B + C - A (the opposite corner of the rectangle).

Algorithm

  1. Store all points in a hash set for O(1) lookup.
  2. For every point A, and for every pair of other points (B, C):
    • Compute vectors AB and AC.
    • Check if AB dot AC = 0 (perpendicular).
    • If yes, compute D = B + C - A.
    • If D exists in the point set, compute the area as |AB| * |AC| and update the minimum.
  3. Return the minimum area found, or 0 if no rectangle exists.

Example Walkthrough

1Initialize: 4 points stored in hash set for O(1) lookup
0
[1,2]
1
[2,1]
2
[1,0]
3
[0,1]
1/6

Code

For each of the n points, we check all O(n^2) pairs of remaining points to see if they form a right angle at that vertex. Many triples fail the perpendicularity check. We are spending time on combinations that can never form rectangles.

What if instead of checking triples, we grouped pairs of points by a property that guarantees they can form a rectangle together?

Approach 2: Diagonal Grouping with Hash Map

Intuition

In any rectangle, the two diagonals bisect each other. That means both diagonals share the same midpoint and have the same length. So if we take all pairs of points and compute their midpoint and distance, any two pairs sharing the same (midpoint, distance) are the two diagonals of a potential rectangle.

Algorithm

  1. For every pair of points (P1, P2), compute the midpoint sum and diagonal length squared.
  2. Group all pairs by the key (midpoint_x_sum, midpoint_y_sum, dist_squared).
  3. For each group with at least 2 pairs, check every combination. Each combination gives 4 points forming a rectangle.
  4. Compute the area using the cross product of the side vectors.
  5. Return the minimum area, or 0 if no rectangle is found.

Example Walkthrough

1Enumerate all 6 pairs, compute (midpoint_sum, dist_squared) for each
(0,1)
(0,2)
(0,3)
(1,2)
(1,3)
(2,3)
1/5

Code