AlgoMaster Logo

Minimum Area Rectangle II

mediumFrequency5 min readUpdated June 23, 2026

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 look for pairs of points that share an x-coordinate or a y-coordinate.

A rectangle is four points where opposite sides are equal and parallel and all four angles are 90 degrees. In coordinate geometry, this implies a property that the efficient solution relies on: the two diagonals of a rectangle bisect each other (they share the same midpoint) and have equal length.

Key Constraints:

  • 1 <= points.length <= 50 → With n at most 50, even an O(n^4) brute force stays under 6.25 million operations, so it runs in time. The O(n^3) and O(n^2) approaches below leave plenty of headroom.
  • 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

Pick any three points and figure out where the fourth corner of the rectangle would have to be. If that fourth point exists in the set, the four points form a rectangle.

Treat one of the three chosen points, A, as the corner holding the right angle. Then the vectors AB and AC must be perpendicular, which the dot product detects: AB dot AC = 0 means the angle at A is 90 degrees. Given that right angle, the opposite corner is fixed at D = B + C - A, because in a rectangle the diagonal from A to D is the sum of the two adjacent sides.

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
0
1
2
1
2
1
2
1
0
3
0
1
1/6

Code

For each of the n points, this checks all O(n^2) pairs of remaining points to test for a right angle at that vertex. Most of those triples fail the perpendicularity check, so much of the work is spent on combinations that can never form a rectangle.

The next approach avoids triples entirely. Instead of testing whether three points happen to form a right angle, it groups pairs of points by a property that two diagonals of the same rectangle must share.

Approach 2: Diagonal Grouping with Hash Map

Intuition

The two diagonals of a rectangle bisect each other and have equal length, so they share both a midpoint and a length. Take every pair of points, treat that pair as a potential diagonal, and record its midpoint and length. Any two pairs that land in the same (midpoint, length) group are two diagonals that meet at a common center with equal length, which is exactly the condition for their four endpoints to form a 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