Maximum Rectangle from Coordinates

Learning Outcome

Turn the Maximum Rectangle from Coordinates interview variant into a clear brute-force baseline, optimized pattern, and implementation plan.

Original Interview Statement

Given points, find the maximum-area rectangle, including tilted rectangles.

Examples

Brute Force Approach

Check every quadruple and test rectangle properties.

Optimized Approach

Two diagonals of a rectangle share the same midpoint and length. Group point pairs by midpoint and squared length; combine pairs in each group.

Exact Pseudocode

for every pair of points:
  key = midpoint sum and dist2
  for previous pair with same key:
    area = abs(cross(p1-p3, p2-p3))
  add pair to group
  

Reference Code

from collections import defaultdict

def max_rectangle_area(points):
    groups = defaultdict(list)
    best = 0
    for i in range(len(points)):
        x1, y1 = points[i]
        for j in range(i + 1, len(points)):
            x2, y2 = points[j]
            key = (x1 + x2, y1 + y2, (x1 - x2) ** 2 + (y1 - y2) ** 2)
            for a, b in groups[key]:
                x3, y3 = points[a]
                x4, y4 = points[b]
                area2 = abs((x1 - x3) * (y2 - y3) - (y1 - y3) * (x2 - x3))
                best = max(best, area2)
            groups[key].append((i, j))
    return best
  

Complexity

Edge Cases

• Duplicate points
• Axis-aligned rectangle
• Tilted rectangle
• Zero area

Follow-ups

• Minimum area rectangle
• Return coordinates

Nearest Practice References

• Minimum Area Rectangle II
• Valid Square

Common Mistakes

• Copying the nearest LeetCode solution without checking the changed rule.
• Skipping duplicate or boundary cases.
• Not stating the brute force before the optimized approach.