Solution: Minimum Area Rectangle

Let’s solve the Minimum Area Rectangle problem using the Math and Geometry pattern.

Statement

You are given an array of points, where point[i] =[xi,yi]= [x_i, y_i] represents a point on a 2D plane.

Your task is to determine the minimum area of a rectangle that can be formed using any four points where the rectangle’s sides are aligned parallel to the X and Y axes. If no such rectangle can be formed, return 00.

Constraints:

  • 1≤1 \leq points.length ≤500\leq 500

  • points[i].length ==2== 2

  • 0≤0 \leq xi ,, yi ≤103\leq 10^3

  • All given points are unique.

Solution

The essence of this solution lies in recognizing that a rectangle is uniquely defined by its diagonally opposite corners, provided the other two required vertices also exist in the set of points. For each pair of points, the solution checks if they can form a diagonal of a rectangle. If so, it verifies the existence of the other two vertices in the point set. When all four vertices are present, the area of the rectangle is calculated, and the minimum rectangle area is updated accordingly.

Using the intuition above, we implement the algorithm as follows:

  1. Store all points in a set using their encoded values, which are calculated using the formula 1009×x+y1009 \times x + y, where xx and yy are the coordinates of a point. This encoding ensures all points are stored in a compact, searchable format, enabling efficient checks for the existence of points later.

We use the formula 1009×x+y1009 \times x + y to uniquely encode each point’s coordinates into a single integer, ensuring efficient storage and quick lookup. Because, as per constraints of the problem, the maximum value of the x- or y-coordinate can be 10001000, we use 10091009 as the closest prime number greater than 10001000.

  1. Initialize a variable, ans, with the maximum integer value. This variable will track the minimum area of a rectangle found during the process.

  2. Use a nested loop to consider all pairs of points. For every pair of points p1 and p2, check if they can form a diagonal of a rectangle. This can be done by checking if the points lie on the same vertical or horizontal line by verifying that their x- and y-coordinates differ.

    1. If the two points can form a diagonal, check if the other two vertices of the potential rectangle exist in the set using their encoded values. The potential rectangle’s other two vertices are given as (xp1,yp2)(x_{p1}, y_{p2}) and (xp2,yp1)(x_{p2}, y_{p1}).

      1. If the other two vertices exist, calculate the area of the rectangle using ∣(xp2−xp1)∣×∣(yp2−yp1)∣|(x_{p2} - x_{p1})| \times |(y_{p2} - y_{p1})|, and update ans with the smaller value between ans and the calculated area.

  3. After iterating through all point pairs, check the value of ans. No rectangle was found if ans is still equal to the maximum integer value, so return 0. Otherwise, return the value of ans as the minimum rectangle area.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.