Skip to main content
Talentd

Minimum Area Rectangle II - Solution & Explanation

MediumArrayMathGeometry15 min readAsked at: Google, Verily
Practice this problem

Problem Statement

You are given an array of points in the X-Y plane points where points[i] = [xi, yi].

Return the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the X and Y axes. If there is not any such rectangle, return 0.

Answers within 10-5 of the actual answer will be accepted.

 

Example 1:

Input: points = [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.

Example 2:

Input: points = [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.

Example 3:

Input: points = [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.

 

Constraints:

  • 1 <= points.length <= 50
  • points[i].length == 2
  • 0 <= xi, yi <= 4 * 104
  • All the given points are unique.

Approach Overview

Problem Overview: You are given a list of 2D points. The task is to find the minimum area rectangle that can be formed using any four of these points as vertices. Unlike the classic axis-aligned version, rectangles here can be rotated at any angle, which makes pure coordinate comparisons insufficient.

Approach 1: Vector Properties and Diagonals (O(n^3) time, O(n^2) space)

A rectangle has two key geometric properties: opposite sides are parallel, and adjacent sides are perpendicular. Pick three points A, B, and C and treat them as potential consecutive vertices. Use vector math to check whether AB is perpendicular to AC using a dot product. If the angle is 90 degrees, compute the fourth point D = B + C - A. Store all points in a hash set for O(1) lookup to verify whether D exists. If it does, compute the rectangle area as |AB| * |AC| and track the minimum. This approach directly uses vector operations from geometry and is easy to reason about during interviews.

Approach 2: Circle Properties and Midpoint (O(n^2 log n) time, O(n^2) space)

Rectangles have equal-length diagonals that share the same midpoint. Iterate through every pair of points and treat them as a potential diagonal. For each pair, compute the midpoint and the squared distance between them. Store pairs in a hash map keyed by (midpoint, diagonal length). Points that share the same key belong to rectangles with the same diagonal. For each group, combine two diagonals to form a rectangle and compute its area using vector cross products. This reduces the search space dramatically because rectangles are detected through shared diagonal properties instead of testing every triple of points. The implementation relies on hashing and pair iteration from array processing and geometric distance calculations from math.

Recommended for interviews: The midpoint + diagonal grouping approach is usually expected in strong solutions. It leverages a geometric invariant (same midpoint and length for diagonals) to reduce the brute-force search from cubic checks to pair grouping. Explaining the vector-based approach first shows geometric understanding, but implementing the diagonal hashing method demonstrates stronger optimization and problem-solving skills.

Approach 1: Vector Properties and Diagonals

This approach focuses on the principle that a rectangle can be formed if two points are opposite corners (diagonals), and we can determine the other two corners by checking the perpendicularity of the vectors and equality of distances. For each pair of points, we calculate midpoints and perpendicular vectors to check for potential rectangle formation.

The solution involves iterating over all triplets of points and checking if they can form an angle of 90 degrees between them using the dot product. If a fourth point exists that complements the orthogonal points, we calculate the area using the determinant of the vectors (base * height), and update the minimum area found. If no such rectangle is found, we return 0.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n^3), given the need to explore all combinations of triplets. Space Complexity: O(n), used for storing points in a set.

Try this approach in the editor →

Approach 2: Circle Properties and Midpoint

Another approach to solving the problem is by leveraging the properties of the midpoint and circle concepts. In this method, for each pair of points considered as the diagonal of a rectangle, we calculate the midpoint and use the Euclidean distance to check for the possibility of a rectangle. This relies on being able to derive potential opposite points based on known diagonals and midpoints.

This Java solution captures the key ideas of using midpoints and organizes pairs by identical midpoints and circle radius. When pairs share these properties, they might form valid rectangle diagonals, thus computing the area between parallel sides.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n^2), since pairs of points are detected, and their midpoints and radii are utilized for hashing. Space Complexity: O(n^2), which arises due to storage of midpoints and circle data.

Try this approach in the editor →

Approach 3: Hash Table + Enumeration

We use a hash table to store all the points, then enumerate three points p_1 = (x_1, y_1), p_2 = (x_2, y_2), p_3 = (x_3, y_3), where p_2 and p_3 are the two endpoints of the diagonal of the rectangle. If the line formed by p_1 and p_2 and the line formed by p_1 and p_3 are perpendicular, and the fourth point (x_4, y_4)=(x_2 - x_1 + x_3, y_2 - y_1 + y_3) exists in the hash table, then we have found a rectangle. At this point, we can calculate the area of the rectangle and update the answer.

Finally, if a rectangle that satisfies the conditions is found, return the minimum area among them. Otherwise, return 0.

The time complexity is O(n^3) and the space complexity is O(n), where n is the length of the array points.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Vector Properties and Diagonals

Time Complexity: O(n^3), given the need to explore all combinations of triplets. Space Complexity: O(n), used for storing points in a set.

Circle Properties and Midpoint

Time Complexity: O(n^2), since pairs of points are detected, and their midpoints and radii are utilized for hashing. Space Complexity: O(n^2), which arises due to storage of midpoints and circle data.

Hash Table + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Vector Properties and DiagonalsO(n^3)O(n^2)Good for understanding rectangle geometry and verifying perpendicular vectors.
Circle Properties and Midpoint GroupingO(n^2 log n)O(n^2)Best general solution. Efficiently detects rectangles using shared midpoint and equal diagonals.

Video Solution

LeetCode 963. Minimum Area Rectangle II Explanation and Solution • happygirlzt • 4,796 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Area Rectangle II easy or hard?
Minimum Area Rectangle II is considered a medium-level problem on LeetCode. The challenge comes from recognizing geometric invariants such as perpendicular vectors or equal diagonals with shared midpoints.
Minimum Area Rectangle II Python/Java solution
Python solutions typically use tuples and dictionaries to hash diagonals, while Java implementations use HashMap with custom keys for midpoint and distance. Both versions follow the same geometric idea: detect rectangles through shared diagonal properties and compute the area using vector math.
How to solve Minimum Area Rectangle II in O(n^2)?
Strict O(n^2) is difficult due to rectangle verification, but near-quadratic solutions are possible. The common method iterates through all point pairs (O(n^2)) and groups them by midpoint and diagonal length, then checks combinations within each group to compute rectangle areas.
What is the best approach for Minimum Area Rectangle II?
The midpoint and diagonal grouping approach is typically the best. It relies on the property that diagonals of a rectangle have the same midpoint and equal length. By hashing point pairs using (midpoint, diagonal length), candidate rectangles can be detected in O(n^2 log n) time instead of checking every triple of points.
Is Minimum Area Rectangle II asked at Google/Amazon/Meta?
Geometry-based point problems like this have appeared in interviews at companies such as Google and Meta. They test vector math, hashing techniques, and the ability to convert geometric properties into efficient algorithms.
What data structure is used in Minimum Area Rectangle II?
The main data structure is a hash map that groups point pairs by midpoint and squared diagonal length. A hash set is also often used for fast point existence checks in vector-based solutions.
What is the time complexity of Minimum Area Rectangle II?
The optimized solution runs in O(n^2 log n) time with O(n^2) space by grouping point pairs that share the same midpoint and diagonal length. A more direct vector-based approach that checks perpendicular triples of points runs in O(n^3) time.

Ready to solve this problem?

Practice Minimum Area Rectangle II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays