0

Largest axis-aligned rectangle from points

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Largest axis-aligned rectangle from points

Companies: Waymo

Difficulty: Hard

Problem statement

You are given a list of distinct points on a 2D integer grid. Each point is a pair [x, y].

Return the largest area of a rectangle whose sides are parallel to the x and y axes and whose four corners are all points in the list. Other points may lie inside the rectangle or on its edges. If no such rectangle exists, return 0.

Implement:

def largest_rectangle_area(points: list[list[int]]) -> int: ...

Constraints

  • 0 <= len(points) <= 2000
  • -10^9 <= x, y <= 10^9
  • Points are distinct.

Example 1

Input:  [[0,0],[0,1],[1,0],[1,1],[4,0],[4,1]]
Output: 4

Three rectangles exist: x in [0,1] (area 1), x in [1,4] (area 3) and x in [0,4] (area 4). The largest is 4.

Example 2

Input:  [[0,0],[1,1],[2,2],[3,0]]
Output: 0

No four points form an axis-aligned rectangle.

Start with a straightforward solution, then improve it. Be ready to discuss what changes if the rectangle must contain no other point.

Approach

A rectangle with sides parallel to the axes is fixed by two x values and two y values. Its four corners are (x1, y1), (x1, y2), (x2, y1), (x2, y2). We need all four to be input points, and we want the largest (x2 - x1) * (y2 - y1). Return 0 when no such rectangle exists.

Brute force. Try every 4-subset of points and test whether it forms an axis-aligned rectangle. That is O(n^4). Say it out loud and move on.

Better: fix the diagonal, O(n^2). Put all points in a hash set. Two points (x1, y1) and (x2, y2) with x1 != x2 and y1 != y2 can be opposite corners. The other two corners are then (x1, y2) and (x2, y1). Check both in the set in O(1). Every rectangle is found (twice, once per diagonal), so the maximum is correct. This is the version most candidates should reach in a phone screen.

Optimal in practice: sweep columns, remember the leftmost column for each y-pair.

  • Group points by x. Sort the x values and visit the columns from left to right.
  • In a column, sort the y values. Every pair (ya, yb) with ya < yb is a possible vertical edge.
  • Keep a dict first_x[(ya, yb)]: the smallest x where that same pair of y values appeared.
  • When the pair shows up again at column x, the two columns form a rectangle of area (x - first_x[(ya, yb)]) * (yb - ya). Do not update first_x. The leftmost column always gives the widest rectangle for that pair, so it is the only partner worth keeping.

Why one partner is enough: for a fixed y-pair, the height is fixed. The area grows with width, and the width for the current column is largest when the other column is the leftmost one. So storing only the first x loses nothing.

The cost is the sum over columns of k^2, where k is the column size. That is O(n^2) in the worst case but much faster when points are spread out. If one axis has many fewer distinct values, sweep along the other axis so the columns are short (swap x and y).

Invariants.

  • After column x is processed, first_x[(ya, yb)] is the smallest column <= x that contains both ya and yb.
  • best is the largest area of any rectangle whose right edge is at a column already processed.

Edge cases. Fewer than four points. All points on one line. Duplicate points (the problem says distinct, but de-duplicate defensively). Negative coordinates. Large coordinates (Python ints do not overflow; in C++ or Java use 64-bit for the area).

Code

from collections import defaultdict
from typing import Dict, List, Sequence, Set, Tuple

Point = Sequence[int]


def largest_rectangle_area(points: List[Point]) -> int:
    """Largest axis-aligned rectangle with all four corners in points; 0 if none."""
    columns: Dict[int, Set[int]] = defaultdict(set)
    for x, y in points:
        columns[x].add(y)

    first_x: Dict[Tuple[int, int], int] = {}
    best = 0
    for x in sorted(columns):
        ys = sorted(columns[x])
        for i in range(len(ys)):
            for j in range(i + 1, len(ys)):
                pair = (ys[i], ys[j])
                if pair in first_x:
                    width = x - first_x[pair]
                    best = max(best, width * (ys[j] - ys[i]))
                else:
                    first_x[pair] = x
    return best


def largest_rectangle_area_diagonal(points: List[Point]) -> int:
    """O(n^2) version: treat each pair of points as a diagonal."""
    pts = list({(x, y) for x, y in points})
    seen: Set[Tuple[int, int]] = set(pts)
    best = 0
    for i in range(len(pts)):
        x1, y1 = pts[i]
        for j in range(i + 1, len(pts)):
            x2, y2 = pts[j]
            if x1 == x2 or y1 == y2:
                continue
            area = abs(x2 - x1) * abs(y2 - y1)
            if area > best and (x1, y2) in seen and (x2, y1) in seen:
                best = area
    return best


if __name__ == "__main__":
    import random

    cases = [
        ([], 0),
        ([[0, 0], [1, 1], [2, 2]], 0),
        ([[0, 0], [0, 2], [3, 0], [3, 2]], 6),
        ([[0, 0], [0, 1], [1, 0], [1, 1], [4, 0], [4, 1]], 4),
        ([[0, 0], [0, 3], [2, 0], [2, 3], [2, 1], [5, 1], [5, 0]], 6),
        ([[-2, -2], [-2, 2], [2, -2], [2, 2], [0, 0]], 16),
        ([[0, 0], [0, 5], [1, 0], [1, 5], [1, 0]], 5),
        ([[0, 0], [1, 0], [2, 0], [3, 0]], 0),
    ]
    for pts, expected in cases:
        assert largest_rectangle_area(pts) == expected, (pts, expected)
        assert largest_rectangle_area_diagonal(pts) == expected, (pts, expected)

    rng = random.Random(7)
    for _ in range(300):
        pts = [[rng.randint(-4, 4), rng.randint(-4, 4)] for _ in range(rng.randint(0, 25))]
        assert largest_rectangle_area(pts) == largest_rectangle_area_diagonal(pts)
    print("ok")

Complexity

Let n be the number of points and k_c the number of points in column c.

  • Column sweep: grouping is O(n), sorting columns and their y values is O(n log n), and the pair loop is O(sum of k_c^2), which is O(n^2) in the worst case (all points on two columns) and close to O(n) when columns are short. Space is O(sum of k_c^2) for the y-pair dict in the worst case, plus O(n) for the columns.
  • Diagonal version: O(n^2) time with O(1) set lookups, O(n) space.
  • Brute force: O(n^4) time, O(1) extra space.

Test cases

  • [] -> 0 (no points).
  • [[0,0],[1,1],[2,2]] -> 0 (fewer than four points, no rectangle).
  • [[0,0],[0,2],[3,0],[3,2]] -> 6 (exactly one rectangle, 3 wide and 2 tall).
  • [[0,0],[0,1],[1,0],[1,1],[4,0],[4,1]] -> 4 (columns 0 and 4 beat columns 0 and 1; shows why we keep the leftmost x for a y-pair).
  • [[0,0],[0,3],[2,0],[2,3],[2,1],[5,1],[5,0]] -> 6 (two rectangles share column 2: 2x3 = 6 and 3x1 = 3).
  • [[-2,-2],[-2,2],[2,-2],[2,2],[0,0]] -> 16 (negative coordinates; the center point does not matter in this version).
  • [[0,0],[0,5],[1,0],[1,5],[1,0]] -> 5 (a duplicate point is ignored).
  • [[0,0],[1,0],[2,0],[3,0]] -> 0 (all collinear).
  • Randomized: both implementations agree on 300 random small grids.

Follow-ups

  1. Smallest area instead of largest (LeetCode 939). Keep the most recent x for each y-pair instead of the first, because the closest column gives the narrowest rectangle. Update last_x[pair] = x every time and take the minimum area.
  2. The rectangle must be empty: no other point inside it or on its edges (LeetCode 3380). Keeping only the leftmost column is no longer safe. For small n, check each candidate with the diagonal method and scan all points for one strictly inside or on an edge, O(n^3). A better plan: only consecutive y values in a column and consecutive x values in a row can form an empty rectangle, so candidates drop to O(n). Verify each candidate by counting points in the box with a 2D prefix count, or offline with a sorted sweep and a Fenwick tree over compressed y, for O(n log n) total. This is the usual "part 2".
  3. Squares only. Add the check x - first_x == yb - ya. Then one partner per pair is no longer enough, so store all columns for each y-pair or use the diagonal method with the extra width-equals-height test.
  4. Rectangles at any angle (LeetCode 963). Two point pairs form a rectangle when they share a midpoint and have the same length (they are its diagonals). Group pairs by (midpoint sum, squared length) and compare all pairs in each group. Area is the product of the two side lengths. This is O(n^2) pairs plus the group sizes.
  5. Very large inputs or a stream of points. Sweep along the axis with fewer distinct values. For streaming inserts, keep columns and update the y-pair dict for the new point only: a new point (x, y) forms pairs with the other y values in column x. Keep both min and max x for each pair, because a new column can now be left of the earlier ones.

Interviewer expectations

Mid-level (L4)

  • Explains the brute force, then reaches the O(n^2) diagonal method with a hash set.
  • Handles no-rectangle (return 0), collinear points and duplicates.
  • Writes working code and walks through one small example by hand.

Senior (L5)

  • Offers the column sweep and explains why keeping only the leftmost column for each y-pair is correct for the maximum (and why it flips to "most recent" for the minimum).
  • Gives the complexity in terms of column sizes, and suggests sweeping the axis with fewer distinct values.
  • Moves to the "no point inside" follow-up and gives a correct, better-than-cubic plan.

Staff (L6+)

  • Gets the emptiness variant to O(n log n) with candidate pruning plus an offline sweep and Fenwick tree, and argues why the pruning keeps every valid rectangle.
  • Generalizes to rotated rectangles and to streaming points, and names the state each needs.
  • Talks about practical limits: memory of the pair dict on dense columns, 64-bit areas in other languages, and how to test with a brute-force oracle on random inputs.

Sign in to comment, vote or remix.