Abstract / Summary

Given rectangles, determine if they together form one complete rectangle without gaps or overlaps.

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 34% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Line Sweep

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 Solution.isRectangleCover method determines whether a collection of axis-aligned rectangles exactly covers a single rectangular region without gaps or overlaps. It does this by first establishing the outer bounds of the combined shape, then verifying that the total area matches the area of the bounding rectangle, and finally by analyzing how the individual rectangle corners are shared. The algorithm relies on simple arithmetic and a hash-map to count corner occurrences, enabling a concise yet thorough validation.

Extent Calculation

minx = min([ r[0] for r in rectangles ])
miny = min([ r[1] for r in rectangles ])
maxx = max([ r[2] for r in rectangles ])
maxy = max([ r[3] for r in rectangles ])

These four statements compute the smallest x-coordinate, smallest y-coordinate, largest x-coordinate, and largest y-coordinate among all rectangles. The resulting (minx, miny) and (maxx, maxy) define the outermost rectangle that would contain every input rectangle. By scanning the list once for each extreme, the code captures the full spatial extent in constant extra space.

Area Verification

need = (maxx - minx) * (maxy - miny)
have = sum((r[2] - r[0]) * (r[3] - r[1]) for r in rectangles)
if need != have:
    return False

need holds the area of the bounding rectangle, while have aggregates the areas of all supplied rectangles. If the two totals differ, the method can immediately reject the configuration because either a gap (missing area) or an overlap (excess area) must exist. This early exit prevents unnecessary work on clearly invalid inputs.

Point Counting

points = defaultdict(int)
for x, y, a, b in rectangles:
    points[(x, y)] += 1      # bottom-left
    points[(x, b)] += 1      # top-left
    points[(a, b)] += 1      # top-right
    points[(a, y)] += 1      # bottom-right

Each rectangle contributes its four corners to a dictionary that maps a coordinate pair to the number of times that corner appears across all rectangles. By incrementing the count for every corner, the algorithm builds a complete picture of how corners are shared. The use of defaultdict(int) eliminates the need for explicit existence checks, streamlining the counting process.

Corner Validation

if points[(minx, miny)] != 1:
    return False
if points[(maxx, miny)] != 1:
    return False
if points[(maxx, maxy)] != 1:
    return False
if points[(minx, maxy)] != 1:
    return False

del points[(minx, miny)]
del points[(maxx, miny)]
del points[(maxx, maxy)]
del points[(minx, maxy)]

The four corners of the outer rectangle must each appear exactly once; any other count would indicate either an overlap at a boundary or a missing corner. After confirming their uniqueness, the code removes these entries so that subsequent checks focus solely on interior points.

Internal Point Validation

for p in points.values():
    if p != 2 and p != 4:
        return False

All remaining points belong to the interior of the cover. A count of 2 signifies that the point is shared by exactly two rectangles along a common edge, while a count of 4 indicates a meeting point of four rectangles. Any other count would betray an irregular sharing pattern, such as a dangling edge or an unexpected overlap, causing the method to reject the configuration.

Edge Cases Handled

The algorithm gracefully handles several subtle situations:

• Overlapping rectangles produce corner counts greater than four, which the final loop detects.
• Gaps leave interior points with a count of zero or one, also caught by the same loop.
• A perfect tiling where rectangles meet only at edges yields interior points with counts of exactly two or four, satisfying the validation.
• The area check catches cases where the total area matches but the arrangement is still invalid, such as a “hole” surrounded by rectangles that collectively fill the outer area.

Performance Optimizations

The implementation achieves efficiency through a few deliberate choices. The use of list comprehensions and generator expressions for computing minima, maxima, and total area ensures that each rectangle is examined only once per operation, avoiding redundant passes. The corner counting loop processes each rectangle in constant time, updating a hash map with O(1) amortized cost per insertion. By deleting the four outer corners before the final verification, the code reduces the number of entries examined in the concluding loop, focusing only on interior points. Overall, the method runs in linear time relative to the number of rectangles while maintaining a modest memory footprint proportional to the distinct corner coordinates encountered.

Imagine you have a big collection of colorful square and oblong building tiles. You want to see if you can put them all together to make one perfectly shaped, giant rectangle without any gaps or holes, and without any of the tiles overlapping like messy layers.

First, the code looks at all the building tiles to find the very edges of the space they occupy. It figures out the smallest point on the far left and bottom, and the largest point on the far right and top. It calculates the area of the giant rectangle that would be formed by those outer corners. Then, it adds up the area of every single tiny tile piece to see if they match. If the total area of the pieces is not the same as the big space, it knows something is wrong.

Next, the code carefully checks every single corner point where the tiles meet. It marks down every corner, and counts how many times each position shows up. If you are fitting tiles together perfectly, where the corners meet inside the shape, they usually connect in pairs or in groups of four. The corners on the very outside of the big giant shape should only appear once. If the middle corners don't have exactly two or four tiles touching them, it means there is a gap or a messy overlap somewhere, and the pieces do not fit together like a perfect puzzle.

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

Time: linear
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		Go			Python
	LeetcodeHelp	C++		Java					Python
	Progiez	C++		Java					Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	halfrost					Go
	haoel	C++
	JoshCrozier		JS
	linouk23	C++
	lzl124631x	C++
	MacJim	C++
	ruoru				Rust
	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
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
linouk23	C++
lzl124631x	C++
MacJim	C++
ruoru	Rust
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