939. Minimum Area Rectangle - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given an array points where each element is a pair [x, y] representing a point in the XY-plane. A rectangle with sides parallel to the x- and y-axes can be formed if there exist four points that form its vertices. The goal is to find the minimum area of such a rectangle. If there is no rectangle that can be formed, return 0.

Example 1:

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4
Explanation:
One valid rectangle is formed by the points [1,1], [1,3], [3,1], and [3,3]. Its area is (3-1) * (3-1) = 4.

Example 2:

Input: points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2
Explanation:
The rectangle with vertices [3,1], [3,3], [4,1], and [4,3] has area (4-3) * (3-1) = 2.

Constraints:

1 ≤ points.length ≤ 500
Each point is a pair of integers.
The coordinates are in a reasonable range (for example, |x|, |y| ≤ 10⁴).

Hints

Hint 1:
The rectangle must have two pairs of points sharing the same x-coordinate and two pairs sharing the same y-coordinate. Think about how you can quickly check whether the other two required corners exist when considering a candidate pair.
Hint 2:
One effective approach is to use a hash set to store the points (using a tuple or similar representation) for O(1) lookups. Then, for any two points that can serve as diagonally opposite corners, check whether the other two corners exist.
Hint 3:
Optimize by iterating over pairs of points and consider only those pairs that are not on the same vertical or horizontal line. Their existence will define the candidate diagonal of a potential rectangle.

Approach: Checking Diagonals with a Hash Set

Idea

Store Points for Quick Lookup:
Insert all points into a set (or hash set) so that you can check in constant time whether a given point exists.
Iterate Over All Pairs of Points:
For each pair of points (p1, p2), treat them as potential diagonal corners of a rectangle. To form a valid rectangle:
- Their x-coordinates must differ.
- Their y-coordinates must differ.
- If so, the other two corners would be: [p1.x, p2.y] and [p2.x, p1.y].
Check for Existence of Other Corners:
For every valid pair (diagonal candidate), use the set to check if both of the other two corners exist. If they do, calculate the area of the rectangle.
Track the Minimum Area:
Keep a variable to store the smallest area encountered. If no rectangle is found, return 0.

Why This Works

By iterating through all pairs, you consider every potential diagonal.
The hash set guarantees that the check for the other two corners is efficient.
Since sides are parallel to the axes, the area calculation is straightforward:
- Area = |p2.x - p1.x| * |p2.y - p1.y|.

Code Implementation

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
- We iterate over all pairs of points. In the worst case, if there are n points, the time complexity is O(n²).
- Checking for the existence of the other two corners is O(1) per pair using the hash set.
- Overall: O(n²).
Space Complexity:
- The hash set stores all points, which takes O(n) space.
- Overall: O(n).

Step-by-Step Walkthrough and Visual Example

Consider the input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]].

Storing Points:
- Insert all points into a set for O(1) lookup:
  - Set = { (1,1), (1,3), (3,1), (3,3), (2,2) }.
Iterate Over Pairs:
- Take points (1,1) and (3,3) as a candidate diagonal.
  - They have different x and y coordinates.
  - Check if the points (1,3) and (3,1) exist in the set. They do.
  - Calculate area = |3 - 1| * |3 - 1| = 2 * 2 = 4.
  - Update the minimum area.
- Other candidate pairs will be checked in a similar fashion, and if a smaller area is found (for example, when points form a rectangle with a smaller width or height), it would update the answer.
Final Answer:
- After all pairs are processed, if at least one rectangle is found, the smallest area is returned. Otherwise, 0 is returned.

7. Common Mistakes and Edge Cases

Common Mistakes

Forgetting to Check Diagonals:
Only pairs with different x and y coordinates can form a valid diagonal. Make sure to filter out pairs that are on the same vertical or horizontal line.
Improper Point Storage:
Using a data structure that does not allow O(1) lookup for checking existence can lead to higher time complexity.
Handling No Rectangle Case:
If no valid rectangle is found, ensure you return 0.

Edge Cases

No Valid Rectangle:
If the points do not form any rectangle, return 0.
Single or Two Points:
When there are fewer than 4 points, it is impossible to form a rectangle, so the output should be 0.

Variations

Maximum Area Rectangle in a Histogram:
A different but related problem where you find the largest rectangle that can be formed in a histogram.
Rectangle Area II:
Another variation that deals with overlapping rectangles.

Longest Increasing Subsequence:
Practice using dynamic programming and binary search.
Points and Lines Problems:
Problems that involve geometry and spatial data structures.