Skip to content

Largest Rectangle from Points

Level: L3-L5 Topics: Geometry, Hash Sets, Enumeration, Optimization

Problem Statement

Given a list of 2D points, find the largest axis-aligned rectangle whose four corners are all points in the given set. Return the area of this rectangle, or 0 if no such rectangle exists.

An axis-aligned rectangle has sides parallel to the x-axis and y-axis.

Background & Constraints

  • Points are given as (x, y) integer coordinates.
  • The rectangle must be axis-aligned (no rotation).
  • "Largest" means maximum area.
  • There may be many points (hundreds or thousands).
  • Duplicate points may or may not be present; clarify with the interviewer.

Examples

Input: [(2,1), (8,1), (2,4), (8,4), (-8,1), (-8,-2), (2,-2), (0,0)]

Rectangle 1: corners (2,1), (8,1), (2,4), (8,4) — width = 6, height = 3, area = 18

Rectangle 2: corners (-8,1), (2,1), (-8,-2), (2,-2) — width = 10, height = 3, area = 30

Output: 30

Hints & Common Pitfalls

  • Store all points in a hash set for O(1) lookup.
  • The key observation: any axis-aligned rectangle is uniquely defined by two points that share the same x-coordinate (a vertical edge) or two points that share the same y-coordinate (a horizontal edge).
  • Approach 1: Group points by x-coordinate. For each pair of points (x, y1) and (x, y2) on the same vertical line, look for another x-value x' such that both (x', y1) and (x', y2) exist. The area is |x - x'| * |y1 - y2|. Track the maximum.
  • Approach 2: Enumerate all pairs of points that could be diagonal corners: (x1, y1) and (x2, y2) where x1 != x2 and y1 != y2. Check if (x1, y2) and (x2, y1) both exist. This is O(N^2) with O(1) lookups.
  • Be careful with negative coordinates — they work fine with hash sets but can trip up array-based approaches.

Follow-Up Questions

  1. Non-aligned rectangles: Find the largest rectangle (any orientation) whose four corners are in the point set. This is significantly harder — you need to check all pairs of points as potential diagonals and verify that the other two corners exist. What geometric property defines the other two corners given a diagonal?
  2. Higher dimensions (3D, KD): Generalize to finding the largest axis-aligned rectangular box in 3D (8 corners from the point set) or hypercube in K dimensions. How does the complexity scale?
  3. Float coordinates: If coordinates are floating-point numbers, how does this affect your hash-based approach? What tolerance or discretization strategy would you use?