Is Minimum Area Rectangle easy or hard?

Minimum Area Rectangle is typically classified as a Medium difficulty problem. The challenge lies in recognizing that rectangles can be detected by matching vertical edge pairs across columns rather than checking every combination of four points.

How to solve Minimum Area Rectangle in O(n^2)?

Group points by their x-coordinate, then sort the y-values within each column. For every pair (y1, y2), store the last x-coordinate where this pair appeared in a hash map. When the pair appears again, compute the rectangle area using the difference in x and y coordinates and update the minimum area.

What is the best approach for Minimum Area Rectangle?

The best approach groups points by x-coordinate and tracks vertical edge pairs (y1, y2) using a hash map. When the same pair appears in another column, it forms a rectangle and the area can be computed instantly. This method runs in O(n^2) time with roughly O(n) space and avoids checking every quadruple of points.

What data structure is used in Minimum Area Rectangle?

The core data structure is a hash map that stores pairs of y-coordinates as keys and the last x-coordinate where the pair appeared as the value. Arrays or lists are used to group points by column, and sorting helps process y-pairs in order.

What is the time complexity of Minimum Area Rectangle?

The optimal solution runs in O(n^2) time. For each column, the algorithm checks all pairs of y-values and uses a hash lookup to see if that pair appeared in a previous column. Space complexity is typically O(n) when using a hash map to store previously seen pairs.

Minimum Area Rectangle Python or Java solution approach?

Both Python and Java implementations follow the same strategy: group points by x-coordinate, generate y-pairs for each column, and store them in a hash map. When a pair reappears in a new column, calculate the rectangle area and update the minimum. The complexity remains O(n^2).

Is Minimum Area Rectangle asked at Google, Amazon, or Meta?

Minimum Area Rectangle is a common geometry and hash map interview problem and has appeared in interviews at companies such as Google, Amazon, and Meta. It tests the ability to recognize geometric patterns and optimize brute-force rectangle detection using hash-based lookups.

Description Solution Video 14:16

939. Minimum Area Rectangle

Medium55.4% acceptance8 companies

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

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

Example 1:

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

Example 2:

Input: points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2

Constraints:

1 <= points.length <= 500
points[i].length == 2
0 <= x_i, y_i <= 4 * 10⁴
All the given points are unique.

Asked at 8 companies

Verily Waymo Flipkart

Google Snapchat Bytedance Microsoft Meta

Topics

14:16

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

939. Minimum Area Rectangle

Asked at 8 companies

Topics

Similar problems