We have a set of points scattered on a 2D plane, and we need to find the smallest rectangle whose sides are parallel to the axes. The phrase "sides parallel to the axes" is the constraint that shapes every approach. It means the rectangle's edges are horizontal and vertical, never tilted. A rectangle is therefore fully determined by choosing two distinct x-coordinates and two distinct y-coordinates, which gives four corners.

The question is then: among all axis-aligned rectangles whose four corners all exist in the point set, which one has the smallest area? If no such rectangle exists, we return 0.

One property drives most of the efficient solutions. An axis-aligned rectangle is defined by exactly two diagonal corners. Given two points that share neither x nor y, the other two corners are forced to be (x1, y2) and (x2, y1). That turns "find four points that form a rectangle" into "find two points and check whether two specific points exist."

Key Constraints:

Intuition

Try every combination of four points and check whether they form an axis-aligned rectangle. Four points qualify when they contain exactly two distinct x-coordinates and exactly two distinct y-coordinates, and every one of the four (x, y) combinations is present.

This is direct to implement but slow. With n up to 500, the number of 4-point combinations is C(500, 4), roughly 2.6 billion, which is far too many.

Algorithm

Example Walkthrough

Code

Most quadruples don't form rectangles, so most of that work is wasted. The next approach picks two diagonal corners and verifies whether the other two exist in a hash set, cutting the search from quadruples to pairs.

Intuition

An axis-aligned rectangle is fully defined by two diagonal corners. Pick two points (x1, y1) and (x2, y2) with x1 != x2 and y1 != y2, and the remaining corners are forced to be (x1, y2) and (x2, y1). So instead of searching for four points that happen to form a rectangle, we iterate over pairs and verify the two forced corners.

We store all points in a hash set for O(1) lookups. For each pair with different x and y coordinates, we check whether (x1, y2) and (x2, y1) both exist. If they do, the four points form a rectangle and we compute its area. This drops the cost from O(n^4) quadruples to O(n^2) pairs, each with O(1) lookups.

Algorithm

Example Walkthrough

Code

This checks every pair as a potential diagonal, but pairs that share an x-coordinate can never be diagonal corners and are wasted work. The next approach groups points by column and looks only at y-pairs shared between columns, which performs much better when points cluster into few columns.

Intuition

Instead of checking all pairs of points, think column by column. Group all points by their x-coordinate. Each group is a list of y-values that share the same x. A rectangle needs two columns (two x-values) that share at least two y-values. So we iterate over pairs of y-values within each column, and for each y-pair we check whether the same y-pair appeared in an earlier column.

Process columns left to right by x-value. For each pair (y1, y2) in the current column, look it up in a map that records, for every y-pair, the x of the column where it last appeared. If the pair is present, the stored x and the current x form a rectangle of height (y2 - y1) and width (currentX - lastX). We then overwrite the stored x with the current one.

Storing only the most recent x is enough to find the minimum area. For a fixed y-pair (fixed height), area grows with width, so the smallest-area rectangle of that height comes from the smallest gap between two columns that contain the pair. Because columns are visited in increasing x order, comparing each column only against the immediately preceding one that held the pair covers the smallest gap for every height: any wider gap would yield a larger or equal area for the same height.

Algorithm

Example Walkthrough

Code