Problem Description

You are given a set of points on a 2D plane, where each point is represented as [x, y] coordinates. Your goal is to find the largest possible rectangle that can be formed using exactly four of these points as corners, with some specific constraints.

The rectangle must satisfy three conditions:

1. Use exactly four points as corners: The rectangle's four corners must be points from the given array.

2. No other points inside or on the boundary: Apart from the four corner points, no other point from the array can be located inside the rectangle or on its edges. The rectangle must be "empty" except for its corners.

3. Axis-aligned edges: The rectangle's sides must be parallel to the x-axis and y-axis (not rotated at an angle).

If such a rectangle exists, return its maximum possible area. If no valid rectangle can be formed following these rules, return -1.

For example, if you have points that can form multiple valid rectangles, you want the one with the largest area. The area is calculated as width × height where width is the difference in x-coordinates and height is the difference in y-coordinates.

Intuition

Since we need to find axis-aligned rectangles, any valid rectangle can be uniquely defined by two opposite corners - specifically, the bottom-left corner and the top-right corner. This is because once we know these two corners, the other two corners are automatically determined (bottom-right and top-left).

The key insight is that we can try all possible pairs of points from our array and treat them as potential opposite corners of a rectangle. For each pair of points (x1, y1) and (x2, y2), we can determine:

• The bottom-left corner would be at (min(x1, x2), min(y1, y2))
• The top-right corner would be at (max(x1, x2), max(y1, y2))

Once we have these potential rectangle boundaries, we need to verify if this forms a valid rectangle according to our constraints. We check every point in the array:

1. If a point is outside the rectangle boundaries, we ignore it
2. If a point is exactly at one of the four corners, we count it
3. If a point is inside the rectangle or on its edges (but not a corner), this rectangle is invalid

A valid rectangle must have exactly 4 points at its corners and no other points inside or on its boundaries.

The brute force approach works here because we're checking all O(n²) pairs of points as potential opposite corners, and for each pair, we verify all n points to check validity. This gives us O(n³) time complexity, which is acceptable for typical constraint sizes.

The area calculation is straightforward: (x_max - x_min) × (y_max - y_min). We keep track of the maximum area found among all valid rectangles.

Learn more about Segment Tree, Math and Sorting patterns.

Solution Approach

The solution implements the enumeration strategy by trying all possible pairs of points as potential opposite corners of a rectangle.

Main Algorithm Structure:

1. Enumerate all pairs of points: The outer loop iterates through each point (x1, y1) with index i, and the inner loop iterates through all previous points (x2, y2) with indices less than i. This ensures we check each pair exactly once.

2. Determine rectangle boundaries: For each pair of points, calculate the actual rectangle corners:

   • Bottom-left corner: (x3, y3) = (min(x1, x2), min(y1, y2))
   • Top-right corner: (x4, y4) = (max(x1, x2), max(y1, y2))

3. Validation function check(x1, y1, x2, y2): This helper function verifies if the rectangle defined by bottom-left (x1, y1) and top-right (x2, y2) is valid:

   • Initialize a counter cnt = 0 to track corner points
   • For each point (x, y) in the array:
     • If the point is outside the rectangle (x < x1 or x > x2 or y < y1 or y > y2), skip it
     • If the point is at a corner (both x equals either x1 or x2 AND y equals either y1 or y2), increment the counter
     • If the point is inside or on the edge but not a corner, return False immediately
   • Return True if exactly 4 corner points were found

4. Area calculation and tracking: If the rectangle is valid:

   • Calculate area as (x4 - x3) * (y4 - y3)
   • Update the maximum area using ans = max(ans, area)

5. Return result: Return the maximum area found, or -1 if no valid rectangle exists (initial value).

Key Implementation Details:

• The use of points[:i] in the inner loop ensures we only check each pair once, avoiding duplicate calculations
• The early return in the check function (return False) immediately invalidates a rectangle if any non-corner point is found within its boundaries
• The condition (x == x1 or x == x2) and (y == y1 or y == y2) precisely identifies corner points
• The algorithm correctly handles the case where the two enumerated points form a diagonal (most common) or are on the same edge of the rectangle

This approach guarantees finding the maximum area rectangle if one exists, as it exhaustively checks all possible rectangle configurations defined by pairs of points.

Example Walkthrough

Let's walk through the solution with a concrete example. Suppose we have the following points:

points = [[1,1], [1,3], [3,1], [3,3], [2,2]]

Step 1: Visualize the points

  3 |  ·     ·
  2 |     ·
  1 |  ·     ·
    +----------
       1  2  3

Step 2: Try pairs as potential opposite corners

Let's trace through a few iterations:

Iteration 1: Consider points [1,1] and [1,3]

• Rectangle boundaries: bottom-left = (1,1), top-right = (1,3)
• This forms a line (width = 0), area = 0
• Check validation: We need 4 corners, but we only have 2 points on this line
• Invalid rectangle

Iteration 2: Consider points [1,1] and [3,1]

• Rectangle boundaries: bottom-left = (1,1), top-right = (3,1)
• This forms a line (height = 0), area = 0
• Invalid rectangle (same reason)

Iteration 3: Consider points [1,1] and [3,3]

• Rectangle boundaries: bottom-left = (1,1), top-right = (3,3)
• Rectangle corners should be: (1,1), (1,3), (3,1), (3,3)
• Area = (3-1) × (3-1) = 4

Validation for this rectangle:

• Check point [1,1]: At corner ✓ (x=1 matches x_min, y=1 matches y_min)
• Check point [1,3]: At corner ✓ (x=1 matches x_min, y=3 matches y_max)
• Check point [3,1]: At corner ✓ (x=3 matches x_max, y=1 matches y_min)
• Check point [3,3]: At corner ✓ (x=3 matches x_max, y=3 matches y_max)
• Check point [2,2]: Inside rectangle but NOT at corner ✗
  • x=2 is between 1 and 3 (not at boundary x=1 or x=3)
  • y=2 is between 1 and 3 (not at boundary y=1 or y=3)
  • This invalidates the rectangle!

Continue with other pairs...

Now let's modify the example to have a valid rectangle:

points = [[1,1], [1,3], [3,1], [3,3], [4,2]]

Checking [1,1] and [3,3] again:

• Rectangle boundaries: bottom-left = (1,1), top-right = (3,3)
• Validation:
  • [1,1]: At corner ✓ (cnt = 1)
  • [1,3]: At corner ✓ (cnt = 2)
  • [3,1]: At corner ✓ (cnt = 3)
  • [3,3]: At corner ✓ (cnt = 4)
  • [4,2]: Outside rectangle (x=4 > x_max=3), skip
• Result: cnt = 4, rectangle is valid!
• Area = 2 × 2 = 4

The algorithm continues checking all other pairs, but this would be the maximum area rectangle found, so the function returns 4.

Solution Implementation

Time and Space Complexity

The time complexity of this algorithm is O(n^3), where n is the length of the array points.

This complexity arises from:

• The nested loops in the main function iterate through all pairs of points, which takes O(n^2) time
• For each pair of points, the check function is called, which iterates through all n points once to verify if they form a valid rectangle
• Therefore, the total time complexity is O(n^2) × O(n) = O(n^3)

The space complexity is O(1) as the algorithm only uses a constant amount of extra space regardless of the input size. The variables ans, cnt, x1, y1, x2, y2, x3, y3, x4, and y4 are all primitive types that don't scale with the input size.

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

Common Pitfalls

1. Incorrect Corner Detection Logic

One of the most common mistakes is incorrectly identifying corner points. Developers often write conditions like:

# WRONG: This uses OR instead of AND
if (x == min_x or x == max_x) or (y == min_y or y == max_y):
    corner_count += 1

This would incorrectly count points that are on the edges but not at corners. For example, a point at (min_x, (min_y + max_y)/2) would be counted as a corner.

Solution: Use AND to ensure the point is at both a boundary x-coordinate AND a boundary y-coordinate:

# CORRECT
if (x == min_x or x == max_x) and (y == min_y or y == max_y):
    corner_count += 1

2. Missing Edge Case: Degenerate Rectangles

The code might not handle cases where the two selected points have the same x or y coordinate, forming a line rather than a rectangle:

# This creates a "rectangle" with zero area
left = min(x1, x2)    # Could equal right if x1 == x2
right = max(x1, x2)

Solution: Add a check to skip degenerate cases:

# Skip if points form a line (zero area)
if x1 == x2 or y1 == y2:
    continue

3. Floating Point Coordinates

If the problem allows floating-point coordinates, direct equality comparisons become unreliable due to precision issues:

# Problematic with floating-point values
if x == min_x or x == max_x:  # May fail due to precision

Solution: Use an epsilon value for floating-point comparisons:

EPSILON = 1e-9

def is_at_boundary(val, boundary1, boundary2):
    return abs(val - boundary1) < EPSILON or abs(val - boundary2) < EPSILON

# Use in validation
if is_at_boundary(x, min_x, max_x) and is_at_boundary(y, min_y, max_y):
    corner_count += 1

4. Inefficient Point Checking Order

Checking all points for every potential rectangle can be inefficient. The current implementation continues checking even after finding an invalid point:

# Current approach checks all points even after finding invalidity
for x, y in points:
    # ... validation logic

While the code does return early on finding an invalid point, the order of checks could be optimized.

Solution: Check the most likely invalid points first (those closest to the rectangle center) or use spatial data structures for large datasets:

# Sort points by distance to rectangle center for earlier rejection
center_x, center_y = (min_x + max_x) / 2, (min_y + max_y) / 2
sorted_points = sorted(points, key=lambda p: 
    abs(p[0] - center_x) + abs(p[1] - center_y))

5. Not Validating All Four Corners Exist

A subtle bug occurs when assuming the four corners exist just because we found a valid rectangle. The code correctly checks for exactly 4 corners, but developers might forget this check:

# WRONG: Assuming corners exist without verification
if no_interior_points:
    return True  # Missing corner count validation

Solution: Always verify both conditions:

# CORRECT: Check both no interior points AND exactly 4 corners
return corner_count == 4  # Implicitly handles no interior points