Introduction

Russian Doll Envelopes is one of the most famous applications of Longest Increasing Subsequence (LIS).

You are given:

envelopes[i] = [width, height]

Goal:

Find the maximum number of envelopes that can be nested inside each other.

Condition:

Both width and height must be strictly greater.

Example

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

Output:

3

Explanation:

[2,3]
→ [5,4]
→ [6,7]

Total Envelopes:

3

Key Observation

A direct 2D LIS solution is:

O(n²)

But we can optimize.

Important Trick

Sort by:

Width  → Ascending
Height → Descending

Example:

[2,3][5,4]
[6,7]
[6,4]

After sorting:

Apply LIS on heights only.

This converts the problem into:

Longest Increasing Subsequence

Why Descending Height?

Consider:

[6,4]
[6,7]

Same width cannot be nested.

Descending height prevents invalid LIS selections.

This is the key interview trick.

Approach : Sorting + LIS

Steps

  1. Sort width ascending.
  2. Sort height descending for equal widths.
  3. Extract heights.
  4. Run Binary Search LIS.
  5. Return LIS length.

Dry Run

Input:

[[5,4], [6,4], [6,7], [2,3]]

Sorted:

[[2,3], [5,4], [6,7], [6,4]]

Heights:

[3,4,7,4]

LIS:

[3,4,7]

Answer:

3

Practice

Complexity Analysis

SortingTime Complexity: O(n log n)
Space Complexity: O(1)

Binary Search LIS
Time Complexity: O(n log n)
Space Complexity: O(n)

Overall
Time Complexity: O(n log n)
Space Complexity: O(n)

Why This Problem is Important

  • LIS Applications
  • Sorting + DP
  • Binary Search Optimization
  • Sequence Problems
  • Advanced DP Thinking

Common Beginner Mistakes

  • Sorting height ascending
  • Ignoring equal widths
  • Applying LIS on width and height together
  • Using O(n²) unnecessarily
  • Forgetting strict comparison

Interview Tip

Always explain:

Sort width ascending. For equal widths,sort height descending.Then run LIS on heights.

This is the key observation interviewers expect.

Related Questions

  • Longest Increasing Subsequence
  • Number of LIS
  • Maximum Length Pair Chain
  • Largest Divisible Subset
  • Box Stacking

Final Takeaway

Russian Doll Envelopes is one of the best examples of transforming a 2D problem into a 1D LIS problem.

It teaches:

  • Sorting Tricks
  • LIS Optimization
  • Binary Search
  • Advanced Dynamic Programming

Mastering this problem greatly improves your ability to recognize hidden LIS patterns in interviews.