Minimum Area Rectangle: Hash Set Geometry

May 25, 20264 min read

leetcodeproblemmediumarrayshash-mapmath

LeetCode 939, Minimum Area Rectangle, gives you a set of points in the x-y plane and asks you to find the smallest axis-aligned rectangle that can be formed using four of those points as corners. If no rectangle exists, return 0.

The key insight is that any axis-aligned rectangle is fully determined by two diagonal corners. If you know two opposite corners, the other two corners are locked in. That means you do not need to check all combinations of four points. You only need to check pairs of two.

Five points on a grid. The four corners [1,1], [1,3], [3,1], [3,3] form the minimum area rectangle with area 4. Point [2,2] is not part of any smaller rectangle.

The hash set approach

Here is the plan:

Store every point in a set so you can check membership in O(1) time.
Iterate over all pairs of points. For each pair, treat them as potential diagonal corners of a rectangle.
Two points can be diagonal corners only if they have different x-coordinates and different y-coordinates. If they share an x or y value, they would form a line segment, not a diagonal.
Given diagonal corners (x1, y1) and (x2, y2), the other two corners must be (x1, y2) and (x2, y1). Check if both exist in the set.
If they do, compute the area as |x1 - x2| * |y1 - y2| and update your running minimum.

This works because every axis-aligned rectangle has sides parallel to the axes. That constraint means the four corners always share coordinates in a predictable way.

Practice this pattern

The solution

class Solution:
    def minAreaRect(self, points: list[list[int]]) -> int:
        point_set = set(map(tuple, points))
        min_area = float("inf")

        for i in range(len(points)):
            x1, y1 = points[i]
            for j in range(i + 1, len(points)):
                x2, y2 = points[j]
                if x1 != x2 and y1 != y2:
                    if (x1, y2) in point_set and (x2, y1) in point_set:
                        area = abs(x1 - x2) * abs(y1 - y2)
                        min_area = min(min_area, area)

        return min_area if min_area != float("inf") else 0

Build the set. Convert each point list to a tuple and store it. Tuples are hashable, so set lookups are O(1).
Iterate pairs. Use a double loop over all pairs of points. This is O(n^2) where n is the number of points.
Filter valid diagonals. Skip pairs that share an x or y coordinate since they cannot be diagonal corners.
Check the other two corners. If (x1, y2) and (x2, y1) are both in the set, you have a valid rectangle.
Track the minimum. Compute the area and compare it against the best so far.

Step-by-step walkthrough

Step 1: Store all points in a set

Convert each [x, y] pair into a hashable form and insert it into a set. This gives us O(1) lookups to check if a point exists.

Step 2: Pick two points as diagonal corners

Iterate over all pairs (p1, p2) where p1.x is not equal to p2.x and p1.y is not equal to p2.y. These could be diagonal corners of a rectangle.

Step 3: Check if the other two corners exist

If (1,1) and (3,3) are diagonal, the other two corners must be (1,3) and (3,1). Look both up in the set. Both exist, so this is a valid rectangle.

Step 4: Compute area and track the minimum

Area = |x1 - x2| * |y1 - y2| = |1 - 3| * |1 - 3| = 4. Compare against the current minimum and update if smaller. After checking all pairs, return the smallest area found.

Drill this with spaced repetition

Complexity analysis

Metric	Value	Why
Time	O(n^2)	Nested loop over all pairs of n points; each pair does O(1) set lookups
Space	O(n)	The set stores all n points

Building blocks

Hash set lookups. The entire approach depends on O(1) membership checks. Without a set, you would need to search through the point list for each candidate corner, pushing the time complexity much higher.
Coordinate geometry for axis-aligned rectangles. If two points are diagonal corners of an axis-aligned rectangle, the other two corners are uniquely determined by swapping their x and y values. This geometric fact eliminates the need to try all combinations of four points.
Reducing a four-element search to a two-element search. By fixing two diagonal corners and deriving the other two, you drop from O(n^4) brute force to O(n^2). Recognizing when you can derive some elements from others is a pattern that appears across many problems.

Edge cases

No valid rectangle exists. If no four points form a rectangle, min_area stays at infinity and you return 0.
Collinear points. If all points lie on a single line (same x or same y), no pair will pass the x1 != x2 and y1 != y2 check, so you correctly return 0.
Duplicate coordinates across points. Multiple points might share the same x or y value. The algorithm handles this naturally because the set lookups are exact coordinate matches.
Large coordinate values. Python handles big integers natively, so there is no overflow risk when computing areas.
Only three corners present. Three out of four corners forming a rectangle will never trigger the area computation, since the missing fourth corner will fail the set lookup.

When the problem restricts rectangles to be axis-aligned (sides parallel to the axes), the diagonal-corner trick always works. For rectangles at arbitrary angles, you would need a different approach entirely.

From understanding to recall

The core trick here is small: two diagonal corners determine the other two. Once you internalize that, the rest of the solution is mechanical (build a set, loop pairs, check corners, track minimum). Practicing with spaced repetition helps you recall this geometric shortcut without having to re-derive it each time. The pattern of "fix some elements, derive the rest, check existence" shows up in many problems beyond rectangles.

Build recall with CodeBricks