939. Minimum Area Rectangle - Detailed Explanation
Problem Statement
You are given an array of points where each point is represented as [x, y]. The task is to find the minimum area of a rectangle formed by any four points from the list such that the rectangle’s sides are parallel to the x- and y-axes. If no rectangle can be formed, return 0.
Example 1
- Input:
[[1,1],[1,3],[3,1],[3,3],[2,2]] - Output:
4 - Explanation:
The rectangle is formed by points (1,1), (1,3), (3,1), and (3,3). Its area is calculated as:
[ \text{Area} = (3-1) \times (3-1) = 4 ]
Example 2
- Input:
[[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]] - Output:
2 - Explanation:
Although one rectangle formed by (1,1), (1,3), (3,1), and (3,3) has area 4, a smaller rectangle is formed by (3,1), (3,3), (4,1), and (4,3). Its area is:
[ \text{Area} = (4-3) \times (3-1) = 2 ]
Example 3
- Input:
[[7,8],[7,10],[9,8],[9,10],[8,9]] - Output:
4 - Explanation:
The rectangle formed by (7,8), (7,10), (9,8), and (9,10) has an area of:
[ \text{Area} = (9-7) \times (10-8) = 4 ]
Constraints
- The number of points is relatively small (e.g., between 1 and 500).
- Each point’s coordinate is an integer.
- All points are unique.
- Rectangle sides must be parallel to the axes.
Hints to Guide Your Approach
-
Axis-aligned Property:
Since the rectangle must have sides parallel to the axes, a valid rectangle is fully determined by two distinct x-coordinates and two distinct y-coordinates. Think about how you can use pairs of x-coordinates (or y-coordinates) to define the boundaries. -
Using a Set or Dictionary:
To quickly check if a particular point exists, consider storing all points in a set (or a dictionary mapping x to a list of y values). This can help you verify the existence of the other two points that would complete a rectangle when you pick a pair of points.
Approaches to Solve the Problem
Approach 1: Brute Force Using Set Membership
Explanation
-
Idea:
Iterate through every pair of points. For each pair that has different x and y coordinates (so they can be diagonal corners), check whether the other two corresponding points exist in the set. -
Key Steps:
- Store all points in a set for constant-time lookups.
- For every pair
(p1, p2)withp1 = (x1, y1)andp2 = (x2, y2), ifx1 != x2andy1 != y2, check if both(x1, y2)and(x2, y1)exist. - If they do, calculate the area and update the minimum found so far.
- Return 0 if no rectangle is found.
Complexity Analysis
- Time Complexity: O(n²) – each pair of points is considered.
- Space Complexity: O(n) – for storing points in a set.
Visual Example
Imagine the points:
(1,1) (3,1)
·--------·
| |
| |
·--------·
(1,3) (3,3)
When you pick (1,1) and (3,3), you check for (1,3) and (3,1). Both exist, so you calculate the area as (3-1) * (3-1) = 4.
Approach 2: Optimal Approach Using Dictionary of Columns
Explanation
-
Idea:
Group points by their x-coordinate. For each x-column, sort the y-coordinates. Then, for each pair of y-coordinates in the same column, record the last x-coordinate seen for that pair. When the same y-pair appears in a new column, you have the potential to form a rectangle. -
Key Steps:
- Build a dictionary where each key is an x-coordinate and the corresponding value is a sorted list of y-coordinates.
- Use another dictionary to remember the last x-coordinate where a particular pair of y-coordinates was seen.
- For each x-coordinate (in sorted order) and for each pair
(y1, y2)in that column, if the pair was seen before, calculate the area using the difference between the current x and the previous x. - Update the minimum area accordingly.
Complexity Analysis
- Time Complexity:
- Grouping points: O(n)
- For each x, if there are k y-coordinates, checking each pair is O(k²). In the worst-case (many points with the same x), the overall time is O(n²), which is acceptable for n ≤ 500.
- Space Complexity: O(n) for the dictionaries.
Visual Example
Imagine two vertical columns:
- Column at x = 1 has y-coordinates [1, 3]
- Column at x = 3 has y-coordinates [1, 3]
For the pair (1, 3), record that it was seen at x = 1. When processing column x = 3, the pair (1, 3) is seen again, so calculate the area as: [ \text{Area} = (3 - 1) \times (3 - 1) = 4 ]
Detailed Code Implementations
Python Code
Below are both the brute force and optimal implementations in Python.
Java Code
Below is the Java implementation with both methods.
Step-by-Step Walkthrough & Visual Examples
Walkthrough of the Brute Force Approach
-
Initialization:
Convert the list of points into a set for O(1) lookups. -
Iterating over Pairs:
For every two points (say, (1,1) and (3,3)), check if they can be diagonally opposite by ensuring they have different x and y coordinates. -
Checking Completeness:
Look up if the other two points, (1,3) and (3,1), exist in the set. If they do, compute the area. -
Updating the Minimum:
Keep track of the smallest area encountered.
Walkthrough of the Optimal Approach
-
Grouping Points:
Map each x-coordinate to a list of its y-coordinates. For example, x = 1 might map to [1, 3]. -
Processing Columns:
For every column (x-value), consider every pair of y-coordinates.
For instance, in column x = 1, the pair (1, 3) is noted. -
Recording and Comparing:
If the same y-pair appears in a later column (say, x = 3), calculate the potential rectangle’s area using the difference in x-values and the y-distance. -
Update Minimum Area:
Keep the smallest area found among all valid rectangles.
Additional Sections
Common Mistakes
-
Not Checking for Distinct Coordinates:
Failing to ensure that the two points selected for the diagonal have different x and y values can lead to errors. -
Double Counting Rectangles:
Without a proper ordering (or using a dictionary to track previous x-coordinates), you might calculate the same rectangle more than once. -
Inefficient Lookups:
Not using a set or a dictionary for quick point lookups can lead to excessive time complexity.
Edge Cases
-
No Rectangle Formed:
When no four points form a valid rectangle, the methods must return 0. -
Single or Two Points:
If there are fewer than four points, it is impossible to form a rectangle.
Alternative Variations & Related Problems
-
Finding the Maximum Area Rectangle:
Instead of the minimum area, one might be asked to find the maximum area rectangle. -
Rectangles Not Necessarily Axis-Aligned:
Problems where rectangles can be rotated add another layer of complexity. -
Related Problems for Further Practice:
- "Valid Rectangle"
- "Largest Rectangle in Histogram"
- "Rectangle Overlap"
- "Maximal Rectangle" (finding the largest rectangle of 1's in a binary matrix)
Complexity Recap
-
Brute Force Approach:
- Time: O(n²)
- Space: O(n)
-
Optimal Approach (Dictionary per Column):
- Time: O(n + (number of columns × k²)) where k is the number of y-values per column (worst-case O(n²))
- Space: O(n)
Both approaches are acceptable given the constraints (n ≤ 500), but the optimal approach often performs better in practice when many points share the same x-coordinate.
GET YOUR FREE
Coding Questions Catalog
