Abstract / Summary

Given a set of points find the smallest area of a rectangle whose corners are all in the set.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 55% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Geometry
• Hash Table
• Math
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the smallest possible area of an axis-aligned rectangle that can be formed from a set of points on a 2-dimensional grid. It returns zero when no such rectangle exists. The algorithm builds auxiliary structures to group points by their x-coordinates and y-coordinates, then iterates over pairs of coordinate lines to discover common orthogonal positions that could serve as opposite sides of a rectangle. Throughout the process it employs a few deliberate choices aimed at reducing the amount of work required for large inputs.

Key Steps

The first logical block initializes the result variable with a positive infinity sentinel and creates two dictionaries that map each y-value to the set of x-values occurring on that horizontal line, and each x-value to the set of y-values occurring on that vertical line.

result = +inf

horizontal = defaultdict(set)
vertical   = defaultdict(set)
for x, y in points:
    horizontal[y].add(x)
    vertical  [x].add(y)

By storing the coordinates in sets, duplicate points are automatically collapsed, and later set operations can be performed efficiently.

The next decision point selects the orientation (horizontal or vertical) that contains fewer distinct lines. This choice reduces the number of outer-loop iterations, because the algorithm will later examine every pair of lines in the chosen orientation.

groups = vertical if len(vertical) < len(horizontal) else horizontal
size = len(groups)

The selected dictionary’s keys are sorted once, producing an ordered list of line identifiers that will be used to generate all unordered pairs.

candidates = sorted(groups)

The core double-loop iterates over each pair of distinct lines. For a given pair a1 and a2, the distance between the lines (a) is computed, representing one side length of a potential rectangle.

for i in range(size):
    for j in range(i + 1, size):
        a1 = candidates[i]
        a2 = candidates[j]
        a  = a2 - a1

The algorithm then finds the intersection of the point sets belonging to the two lines. This intersection yields the coordinates that are shared by both lines, i.e., the positions where a vertical (or horizontal) side could be placed on both lines simultaneously. The intersection is sorted to enable straightforward computation of the minimal distance between any two adjacent shared coordinates.

both = sorted(groups[a1] & groups[a2])

If at least two common coordinates exist, the smallest gap between consecutive shared coordinates (b) is determined. This gap corresponds to the other side length of the rectangle. The area candidate (a * b) is compared with the current best result, and the minimum is retained.

if len(both) >= 2:
    b = min([ b2 - b1 for b1, b2 in zip(both, both[1 :]) ])
    result = min(result, a * b)

Finally, the function returns the computed minimal area if a rectangle was found; otherwise it returns zero.

return result if result != +inf else 0

Edge Cases Handled

When the input list is empty or contains fewer than four distinct points, the dictionaries will have few or no keys, causing the outer loops to execute zero times. Consequently result remains at its infinity sentinel, and the function returns zero, correctly indicating that no rectangle can be formed.

If all points lie on a single horizontal or vertical line, the intersection of any two distinct lines will be empty, again leaving result unchanged and leading to a zero return value.

Duplicate points are automatically ignored because each coordinate is stored in a set. This prevents spurious intersections that could otherwise be counted multiple times.

When multiple rectangles are possible, the algorithm examines every pair of lines and every pair of shared coordinates, guaranteeing that the smallest area among all feasible rectangles is selected.

Performance Optimizations

The most noticeable optimization is the selection of the smaller of the two grouping dictionaries (vertical vs horizontal). By iterating over the orientation with fewer distinct lines, the number of line-pair combinations processed is minimized, which can be significant when the point distribution is highly skewed (e.g., many points share the same x-coordinate but have many distinct y-coordinates).

Using sets for the coordinate collections enables fast intersection operations (groups[a1] & groups[a2]). Set intersection runs in time proportional to the size of the smaller set, which further reduces work when the two lines have few common points.

Sorting the keys of the chosen dictionary once (candidates = sorted(groups)) avoids repeated ordering work inside the nested loops. The inner sorting of the intersection (both = sorted(...)) is performed only when an intersection exists, and the sorted list is then used to compute adjacent differences in a single pass via a list comprehension combined with zip. This approach eliminates the need for nested loops over the intersection elements.

The use of a sentinel (+inf) for the result allows the algorithm to keep track of the best area found without needing an additional flag variable, simplifying the final conditional return.

Imagine these points are bright stars scattered across the night sky. The goal is to connect four of these stars to draw a perfect rectangle with the smallest possible size.

First, the code organizes the stars into neat rows and columns. It keeps a list for every horizontal line and every vertical line to remember exactly where each star is sitting. This makes finding the stars much easier later on.

Next, the code looks at two rows or two columns at a time to see if they share any stars. If two lines have at least two stars in the same positions, those stars form the corners of a rectangle.

The code then calculates how wide and tall that rectangle is by checking the distance between the lines and the distance between the stars. It repeats this process for all the different lines. By comparing all the rectangles found this way, the code keeps track of the smallest one it discovers. Finally, if any rectangles were found, the size of the tiniest one is chosen. If no four stars could ever form a rectangle, the result is zero.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python			TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java			Python		Go
	LeetcodeHelp	C++		Java			Python
	Progiez	C++		Java			Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fengvyi	C++
	fsq	C++
	JoshCrozier		JS
	lkwq007						Python
	lzl124631x	C++
	MacJim	C++
	martianoff					Scala
	suxrobGM				C#
	varunu28			Java
	vli02							C
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
lzl124631x	C++
MacJim	C++
martianoff	Scala
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality