Problem Description

You are given a set of points on a 2D coordinate plane, where each point is represented as [x, y] coordinates. Your task is to find the minimum area of a rectangle that can be formed using these points as corners, with the constraint that the rectangle's sides must be parallel to the X and Y axes (meaning the rectangle cannot be rotated).

To form a valid rectangle, you need exactly 4 points that create two pairs of coordinates:

• Two points sharing the same x-coordinate but different y-coordinates (forming one vertical side)
• Two other points sharing a different x-coordinate but having the same y-coordinates as the first pair (forming the opposite vertical side)

The area of such a rectangle would be calculated as width × height, where:

• Width = difference between the x-coordinates of the vertical sides
• Height = difference between the y-coordinates of the horizontal sides

If no such rectangle can be formed from the given points, return 0.

For example, if you have points [[1,1], [1,3], [3,1], [3,3]], they form a rectangle with:

• Width = 3 - 1 = 2
• Height = 3 - 1 = 2
• Area = 2 × 2 = 4

The goal is to find the rectangle with the minimum possible area among all valid rectangles that can be formed.

Intuition

To find rectangles with sides parallel to the axes, we need to identify sets of 4 points that form opposite corners. A key observation is that for any rectangle, we can think of it as having two vertical lines at different x-coordinates, with each vertical line containing exactly two points at the same y-coordinates.

Let's think about how to efficiently find rectangles. If we process points by their x-coordinates from left to right, we can look for pairs of points that share the same x-coordinate (forming a vertical line segment). For each such vertical line segment defined by points (x, y1) and (x, y2), we want to check if we've seen this same pair of y-coordinates (y1, y2) at a previous x-coordinate.

If we have seen (y1, y2) at some previous x-coordinate x', then we've found a rectangle! The four corners would be (x', y1), (x', y2), (x, y1), and (x, y2). The area would be (x - x') × (y2 - y1).

The strategy becomes:

1. Group all points by their x-coordinates
2. Process these x-coordinates in sorted order (left to right)
3. For each x-coordinate, look at all pairs of y-coordinates at that x
4. Check if we've seen each pair (y1, y2) before at a previous x-coordinate
5. If yes, calculate the area and update our minimum
6. Record this pair (y1, y2) with the current x-coordinate for future rectangles

By processing x-coordinates in sorted order and storing the most recent x-coordinate for each y-pair, we ensure that we're always calculating the smallest possible width when we find a matching pair, which helps us find the minimum area efficiently.

Learn more about Math and Sorting patterns.

Solution Approach

The implementation follows the intuition by systematically processing points grouped by x-coordinates:

Step 1: Group points by x-coordinate

d = defaultdict(list)
for x, y in points:
    d[x].append(y)

We use a dictionary d where each key is an x-coordinate and the value is a list of all y-coordinates at that x. This allows us to efficiently find all points on the same vertical line.

Step 2: Initialize tracking variables

pos = {}
ans = inf

• pos dictionary stores pairs of y-coordinates as keys and their most recent x-coordinate as values. Format: {(y1, y2): x}
• ans tracks the minimum area found, initialized to infinity

Step 3: Process x-coordinates in sorted order

for x in sorted(d):
    ys = d[x]
    ys.sort()

We process x-coordinates from left to right (sorted order) and sort the y-coordinates at each x to ensure consistent pair ordering.

Step 4: Check all pairs of y-coordinates at current x

for i, y1 in enumerate(ys):
    for y2 in ys[i + 1:]:

For each x-coordinate, we examine all pairs of points (x, y1) and (x, y2) where y1 < y2. These pairs form vertical line segments.

Step 5: Check for rectangle completion and update

if (y1, y2) in pos:
    ans = min(ans, (x - pos[(y1, y2)]) * (y2 - y1))
pos[(y1, y2)] = x

• If we've seen the pair (y1, y2) before at some x-coordinate stored in pos, we've found a rectangle
• Calculate area: width (x - pos[(y1, y2)]) × height (y2 - y1)
• Update the minimum area if this rectangle is smaller
• Store/update the current x-coordinate for this y-pair for future rectangles

Step 6: Return result

return 0 if ans == inf else ans

If no rectangle was found, ans remains infinity, so we return 0. Otherwise, return the minimum area found.

The time complexity is O(n²) where n is the number of points, as we potentially check all pairs of points at each x-coordinate. The space complexity is O(n) for storing the point groupings and y-coordinate pairs.

Example Walkthrough

Let's walk through the solution with points: [[1,1], [1,3], [3,1], [3,3], [4,1], [4,3]]

Step 1: Group points by x-coordinate

d = {1: [1, 3], 3: [1, 3], 4: [1, 3]}

Step 2: Initialize tracking

pos = {}  # Will store (y1, y2) pairs and their x-coordinates
ans = inf  # Minimum area tracker

Step 3: Process x = 1 (first x-coordinate)

• Points at x=1: [1, 3] (already sorted)
• Check pair (1, 3):
  • Not in pos yet, so no rectangle can be formed
  • Store: pos[(1, 3)] = 1
• Current state: pos = {(1, 3): 1}, ans = inf

Step 4: Process x = 3

• Points at x=3: [1, 3] (already sorted)
• Check pair (1, 3):
  • Found in pos! Previous x was 1
  • Rectangle corners: (1,1), (1,3), (3,1), (3,3)
  • Area = (3 - 1) × (3 - 1) = 2 × 2 = 4
  • Update: ans = min(inf, 4) = 4
  • Update: pos[(1, 3)] = 3
• Current state: pos = {(1, 3): 3}, ans = 4

Step 5: Process x = 4

• Points at x=4: [1, 3] (already sorted)
• Check pair (1, 3):
  • Found in pos! Previous x was 3
  • Rectangle corners: (3,1), (3,3), (4,1), (4,3)
  • Area = (4 - 3) × (3 - 1) = 1 × 2 = 2
  • Update: ans = min(4, 2) = 2
  • Update: pos[(1, 3)] = 4
• Final state: pos = {(1, 3): 4}, ans = 2

Step 6: Return result Return 2 (the minimum area found)

The algorithm found two rectangles:

• Rectangle 1: width=2, height=2, area=4
• Rectangle 2: width=1, height=2, area=2 (minimum)

By processing x-coordinates in sorted order and always storing the most recent x for each y-pair, we ensure we're finding the smallest width (and thus potentially smallest area) rectangles as we progress.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2)

The algorithm works as follows:

• First, it groups points by their x-coordinates in a dictionary: O(n) where n is the number of points
• Sorting the x-coordinates: O(k log k) where k is the number of unique x-coordinates, and k ≤ n
• For each x-coordinate, it sorts the y-values: The total cost across all x-coordinates is O(n log n) in the worst case
• The nested loops iterate through pairs of y-values for each x-coordinate:
  • In the worst case, all points could share the same x-coordinate, leading to O(n^2) pairs
  • For each pair (y1, y2), checking if it exists in the dictionary and updating takes O(1)
• Overall: O(n) + O(n log n) + O(n^2) = O(n^2)

Space Complexity: O(n)

The space usage includes:

• Dictionary d storing all points grouped by x-coordinate: O(n)
• Dictionary pos storing pairs of y-coordinates: In the worst case, we could have O(n^2) unique pairs, but since we only store the most recent x-coordinate for each pair, and we process x-coordinates in sorted order, the actual number of stored pairs at any time is bounded by the number of possible y-coordinate pairs across all x-coordinates, which is O(n) in total
• Sorted list of y-values: O(n) across all iterations
• Overall: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Duplicate Points

One common pitfall is not considering that the input might contain duplicate points. If the same point appears multiple times in the input, it could lead to incorrect behavior when forming rectangles.

Problem Example:

points = [[1,1], [1,1], [1,3], [3,1], [3,3]]  # [1,1] appears twice

Solution: Convert the points list to a set first to remove duplicates:

def minAreaRect(self, points: List[List[int]]) -> int:
    # Remove duplicates by converting to set of tuples
    points = list(set(map(tuple, points)))
  
    # Continue with the rest of the algorithm...
    x_to_y_coords = defaultdict(list)
    for x, y in points:
        x_to_y_coords[x].append(y)
    # ...

2. Integer Overflow with Large Coordinates

When calculating the area, if the coordinates are very large (near the limits of integer range), the multiplication (x2 - x1) * (y2 - y1) might cause integer overflow in some languages. While Python handles arbitrary precision integers automatically, this could be an issue when porting to other languages.

Problem Example:

points = [[0, 0], [0, 1000000000], [1000000000, 0], [1000000000, 1000000000]]
# Area = 1000000000 * 1000000000 = 10^18

Solution: In Python, this is handled automatically, but be aware of the constraint limits. In other languages, use appropriate data types (like long long in C++) or check for overflow conditions.

3. Incorrect Y-Pair Ordering

A subtle pitfall is not maintaining consistent ordering when creating y-coordinate pairs. If you don't sort the y-coordinates or ensure y1 < y2, you might store the same pair as both (y1, y2) and (y2, y1), treating them as different pairs.

Problem Example:

# Without proper ordering, these could be treated as different pairs:
# At x=1: pair (1, 3)
# At x=5: pair (3, 1)  # Same pair but reversed!

Solution: Always ensure consistent ordering by sorting y-coordinates and maintaining y1 < y2:

y_coords.sort()  # Sort first
for i, y1 in enumerate(y_coords):
    for y2 in y_coords[i + 1:]:  # This ensures y1 < y2
        # Process the pair (y1, y2)

4. Not Updating the X-Coordinate for Previously Seen Y-Pairs

Some might think that once a rectangle is found with a y-pair, we shouldn't update the x-coordinate for that pair. However, we need to update it because the same y-pair at the current x might form a smaller rectangle with a future x-coordinate.

Problem Example:

points = [[1,1], [1,3], [3,1], [3,3], [5,1], [5,3]]
# Y-pair (1,3) appears at x=1, x=3, and x=5
# Rectangle 1: x=1 to x=3, area = 2*2 = 4
# Rectangle 2: x=3 to x=5, area = 2*2 = 4
# If we don't update x=3 for pair (1,3), we miss the second rectangle

Solution: Always update the x-coordinate after checking for rectangles:

if (y1, y2) in y_pair_to_last_x:
    # Calculate area with previous x
    area = (current_x - y_pair_to_last_x[(y1, y2)]) * (y2 - y1)
    min_area = min(min_area, area)

# Always update to current x for future rectangles
y_pair_to_last_x[(y1, y2)] = current_x