What is the optimal approach and complexity for Russian Doll Envelopes?

Sort by width ascending, height descending on ties; then the O(N log N) strict LIS on heights with lower_bound with optimal time complexity O(N log N) and space complexity O(N).

How do you identify the pattern for Russian Doll Envelopes?

Look for key signals in the prompt: "fits inside another" indicates Both width and height must be strictly smaller. This is a 2D rule: one side alone is not enough.; "nest as many as you can" indicates We want the longest chain, so the answer is a count of envelopes in one chain.; "cannot rotate" indicates Width and height are fixed. Swapping them is not allowed, so the sort must use each side in its own role..

Russian Doll Envelopes

Hard·LeetCode #354 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

You have a pile of envelopes. Each one has a width and a height. Envelope A can go inside envelope B only when both the width and the height of A are strictly smaller than those of B. You may not turn an envelope.

Nest as many envelopes as you can in one chain, one inside the next. Return the largest number of envelopes in such a chain.

Input

envelopes: a list of [w, h] pairs, one pair for each envelope.

Output

The largest number of envelopes in one nest.

Example 1

Input: envelopes = [[5, 4], [6, 4], [6, 7], [2, 3]]

Output: 3

The chain [2, 3] → [5, 4] → [6, 7] works: each envelope is strictly smaller in width and in height than the next one.

Example 2

Input: envelopes = [[1, 1], [1, 1], [1, 1]]

Output: 1

Equal envelopes do not fit inside each other, so only one of them can be used.

Constraints

• 1 ≤ envelopes.length ≤ 10^5
• envelopes[i].length == 2
• 1 ≤ wᵢ, hᵢ ≤ 10^5

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“fits inside another”

→ Both width and height must be strictly smaller. This is a 2D rule: one side alone is not enough.

“nest as many as you can”

→ We want the longest chain, so the answer is a count of envelopes in one chain.

“cannot rotate”

→ Width and height are fixed. Swapping them is not allowed, so the sort must use each side in its own role.

Approach Complexity Ladder

Brute Force — try every chain of envelopes that fitO(N · 2^N)O(N)

Recurse: from the current outer envelope, try each envelope that fits strictly inside it; keep the longest chain

Better — O(N²) dp: longest chain whose outermost envelope is iO(N²)O(N)

Sort by width, then height; dp[i] = 1 + the best dp[j] over earlier envelopes that fit strictly inside i

Optimal — sort (width asc, height desc), then strict LIS on heightsO(N log N)O(N)

Sort by width ascending, height descending on ties; then the O(N log N) strict LIS on heights with lower_bound

Brute Force Intuition

Choose an outermost envelope, then recurse on the envelopes that fit strictly inside it on both sides. Try every choice and keep the longest chain. An envelope with an equal width or an equal height never fits, so the check is two strict comparisons.

Recognition rule for this sub-pattern:

Sort by one dimension (ties broken carefully), then run LIS on the other.

Remember this · DP — Longest Increasing Subsequence

Trigger

Longest chain where each item must be bigger/fit inside the previous one (numbers, pairs, envelopes, words).

Think

Does each element extend the best chain ending at some smaller earlier element?

Key question

Sort first? Then what does "increasing" mean for these items?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Longest Increasing Subsequence translate into production architectures and low-level memory mechanics.

LLD Architecture