Abstract / Summary

Find the longest set of envelopes that can be nested inside each other based on their size.

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 38% (700k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Dynamic Programming
• 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 solves the classic “Russian Doll Envelopes” problem by converting it into a longest increasing subsequence (LIS) task on envelope heights after a careful ordering of the envelopes. The algorithm proceeds in three logical phases: ordering the input, extracting a monotonic sequence of heights, and applying a binary-search-based LIS construction. Each phase is compactly expressed, yet together they deliver an efficient solution for large collections of envelopes.

Ordering the Envelopes

The first operation arranges the envelopes so that a simple scan of heights yields a valid LIS candidate.

envelopes.sort(key = lambda x : x[0] * 10**6 - x[1])

The key function multiplies the width by a large constant (one million) and subtracts the height. This effectively sorts envelopes primarily by width in ascending order while ordering equal-width envelopes by height in descending order. The descending height order for identical widths prevents the algorithm from mistakenly nesting envelopes that share the same width, because the subsequent LIS step will never see an increasing height for those items.

Building the Height Sequence

After sorting, the code iterates through the ordered list, extracting the height component of each envelope.

heights = []  # store minimum heights
for w, h in envelopes:
    pos = bisect_left(heights, h)
    if pos == len(heights):
        heights.append(h)  # largest so far
    else:
        heights[pos] = h  # may overwrite h by itself, too, but often reduces it

During each iteration, a binary search (bisect_left) determines the leftmost position where the current height can be placed while preserving a non-decreasing order in the heights list. If the height is larger than any element already stored, it extends the list, representing a longer increasing subsequence. Otherwise, the height replaces the element at the found position, ensuring that the tail of a subsequence of a given length remains as small as possible. This replacement step is crucial: a smaller tail leaves more room for future heights to extend the subsequence.

Edge Cases Handled

The sorting key’s descending tie-breaker naturally addresses the situation where multiple envelopes share the same width. By placing the tallest among them first, any later envelope with the same width will have a height that is not larger, causing the binary-search step to replace rather than extend the subsequence, thereby preventing an illegal nesting.

When the input list is empty, the initial heights list remains empty, and the final len(heights) correctly returns zero.

If all envelopes have identical dimensions, the sort order groups them together, and the binary search always finds position zero, repeatedly overwriting the first entry. The algorithm therefore yields a length of one, reflecting that only a single envelope can be chosen.

When heights are strictly decreasing after sorting (for example, widths increase while heights decrease), each height will replace the first element, and the final length will be one, correctly indicating that no nesting beyond a single envelope is possible.

Performance Optimizations

The custom sort key avoids the need for a tuple-based key and leverages integer arithmetic to achieve the required primary-secondary ordering in a single pass. By scaling the width with a large constant, the code ensures that width differences dominate the comparison, while the subtraction of height imposes the reverse ordering for equal widths.

The use of bisect_left on a dynamically maintained list of tail heights provides logarithmic search time for each envelope, eliminating the need for a full scan of the current subsequence list.

Replacing elements in the heights list rather than inserting preserves the list’s size growth strictly to the length of the longest valid nesting, which caps memory usage to the optimal answer size.

Overall, the combination of a single sort, a linear scan, and binary searches yields a solution that scales well with the number of envelopes, delivering fast execution even for large inputs.

Imagine you have a big pile of envelopes of all different sizes, and you want to see how many you can fit inside each other like a set of nesting dolls. To make this work, the smaller envelope must always be both thinner and shorter than the one holding it.

First, the code organizes all the envelopes by lining them up from the thinnest to the widest. If two envelopes are the same width, it puts the taller one first so that they do not accidentally fit inside each other when they should not.

Next, a new, empty list is created to act like a track for keeping track of the heights of the envelopes that are currently fitting inside one another. The code looks at each envelope one by one and checks its height. It searches through the list to find the best place for that height to go. If the height is taller than anything already in the list, it gets added to the end, which shows that another envelope has been successfully added to the stack. If the height is not taller, it finds a spot where it can replace a larger number with a smaller one. By making the numbers in the list as small as possible, there is more room for other envelopes to fit later on. After looking at every envelope in the original pile, the total count of numbers in the list shows the longest possible chain of envelopes.

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

Time: loglinear
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++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java			Go
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	begeekmyfriend									C
	black-shadows	C++
	charles-wangkai				Java
	chenyanzhe	C++
	everthis			JS
	fengvyi	C++
	fpdjsns	C++
	gouthampradhan				Java
	halfrost							Go
	JoshCrozier			JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	martianoff					Scala
	ruoru						Rust
	suxrobGM								C#
	trung-hn		Python
	wisdompeak	C++
	XiaotaoGuo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
begeekmyfriend	C
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fengvyi	C++
fpdjsns	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
MacJim	C++
martianoff	Scala
ruoru	Rust
suxrobGM	C#
trung-hn	Python
wisdompeak	C++
XiaotaoGuo	C++
zfang399	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