Minimum Area Rectangle

Minimum Area Rectangle is a classic geometry-meets-hashing problem. The trick is realizing you do not need to test all four corners at once — a hash set lets you confirm a rectangle from just two of them.

The slow way first

The obvious idea: try every group of four points and check whether they form an axis-aligned rectangle. That is O(n⁴) — far too slow. Even being clever about which four to pick, brute force over corners explodes quickly.

The question to ask: what is the smallest amount of information that pins down a whole rectangle? For an axis-aligned rectangle, one diagonal is enough. Two opposite corners (x1, y1) and (x2, y2) completely determine the other two corners: they must be (x1, y2) and (x2, y1).

The idea: a diagonal plus two lookups

Put every point into a hash set. Then loop over pairs of points and treat each pair as a possible diagonal. A pair is only a diagonal if the two points differ in both x and y (otherwise they share a side, not a diagonal). For a real diagonal, the other two corners are forced — so just look them up in the set. If both are present, you have a rectangle, and its area is |x2 − x1| · |y2 − y1|. Keep the minimum.

The key insight: a diagonal is the cheapest fingerprint of a rectangle. Two stored corners plus two O(1) lookups confirm or reject it instantly, so we only ever loop over pairs — not quads.

Walk through it

Step through the animation. The points sit on a small grid. We pick diagonal A(1,1)–D(3,3) first: the missing corners (1,3) and (3,1) are both in the set, so area = 2·2 = 4 and best becomes 4. Then diagonal A(1,1)–F(4,3) also forms a rectangle, but area 3·2 = 6 is larger, so best stays 4. Pairs that share an x or a y are skipped because they cannot be a diagonal. The minimum that survives is 4 — the tight square.

Pseudocode

put every point into a set called "seen"
best = infinity
for each point (x1, y1):
    for each point (x2, y2):
        if x1 == x2 or y1 == y2:      # same row/column -> not a diagonal
            skip
        if (x1, y2) in seen and (x2, y1) in seen:
            area = |x2 - x1| * |y2 - y1|
            best = min(best, area)
return best if a rectangle was found, else 0

The Python solution

def min_area_rect(points):
    seen = {(x, y) for x, y in points}
    best = float("inf")
    for x1, y1 in points:
        for x2, y2 in points:
            if x1 == x2 or y1 == y2:
                continue
            if (x1, y2) in seen and (x2, y1) in seen:
                area = abs(x2 - x1) * abs(y2 - y1)
                best = min(best, area)
    return best if best < float("inf") else 0

• seen is a set of (x, y) tuples — that is what makes the corner checks O(1).
• The double loop walks every ordered pair of points as a candidate diagonal.
• x1 == x2 or y1 == y2 filters out pairs that share a side; only true diagonals survive.
• Line 8 is the heart: (x1, y2) and (x2, y1) are the other two corners, looked up directly.
• When both exist we compute |dx·dy| and fold it into best with min.
• If best never changed, no rectangle was found, so we return 0.

Complexity

We trade O(n) extra space (the set of points) for a huge speed win: O(n⁴) → O(n²). That move — store the points and confirm a shape from a partial fingerprint — is the heart of most computational-geometry-on-a-grid problems.

When this pattern shows up

Practice