Minimum Area Rectangle

Minimum Area Rectangle

What is this problem about?

The Minimum Area Rectangle problem gives you a list of coordinates (x, y) on a 2D plane. You need to find the minimum area of a rectangle formed from these points, such that the rectangle's sides are parallel to the X and Y axes. If no such rectangle can be formed, you return 0.

Why is this asked in interviews?

This is a classic Minimum Area Rectangle interview question asked at Google, Meta, and Flipkart. It tests your ability to use Hash Tables for fast lookups and your geometric reasoning. It evaluates if you can identify that a rectangle is uniquely defined by its diagonal points (x1, y1) and (x2, y2).

Algorithmic pattern used

The Hash Table interview pattern is crucial here.

1. Put all points into a Set for $O(1)$ lookup.
2. Iterate through every pair of points p1 and p2.
3. If p1.x != p2.x and p1.y != p2.y, they could be the diagonal of a rectangle.
4. Check if the other two required corners, (p1.x, p2.y) and (p2.x, p1.y), exist in your Set.
5. If they do, calculate the area |p1.x - p2.x| * |p1.y - p2.y| and track the minimum.

Example explanation

Points: (1,1), (1,3), (3,1), (3,3), (4,1), (4,3).

1. Pick (1,1) and (3,3) as diagonals.
2. Check if (1,3) and (3,1) exist. They do! Area = 2 * 2 = 4.
3. Pick (3,1) and (4,3) as diagonals.
4. Check if (3,3) and (4,1) exist. They do! Area = 1 * 2 = 2.
5. The minimum area found is 2.

Common mistakes candidates make

• O(N^4) Brute Force: Trying to pick four points and check if they form a rectangle. This is far too slow for a large number of points.
• Not checking parallel sides: Trying to find any rectangle (including tilted ones), but the problem usually specifies sides must be parallel to the axes.
• Incorrect lookup structure: Using a nested list for lookups instead of a Hash Set of strings or tuples, making the point check $O(N)$ instead of $O(1)$.

Interview preparation tip

Geometry problems in coding interviews often boil down to Hash Table lookups. If you can define a shape by a subset of its points (like a diagonal for a rectangle or a center/radius for a circle), you can use the Set to verify the existence of the remaining points.