NeetCode #684LC-354Hard1-D Dynamic Programming
← Back to All Problems#684 · #354 · Russian Doll Envelopes(俄罗斯套娃信封问题)
📌 Problem Statement & Constraints
You are given a 2-D array
envelopes of [width, height] pairs. An envelope can be placed inside another only if both its width and height are strictly smaller. Return the maximum number of envelopes that can be nested. Constraints: 1 <= envelopes.length <= 10^5, 1 <= width_i, height_i <= 10^5.💡 Core Algorithmic Approaches
- Sort by width ascending; for equal widths, sort height in descending order.
- The problem then becomes a longest strictly increasing subsequence on the heights.
- The descending tie-break ensures two envelopes of equal width can never both be selected, since their heights appear in decreasing order.
- Solve the LIS on heights with patience sorting in O(n log n).
💻 Benchmark Python3 Implementation
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
from bisect import bisect_left
# width asc; equal widths by height desc so equal widths cannot both be used
envelopes.sort(key=lambda e: (e[0], -e[1]))
tails = []
for _, h in envelopes:
i = bisect_left(tails, h)
if i == len(tails):
tails.append(h)
else:
tails[i] = h
return len(tails)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort plus the patience-sorting LIS.
💾 Space Complexity
O(n): the tails array.
⚠️ Interview Pitfalls & Follow-ups
- Sorting heights ascending for equal widths: that would allow two equal-width envelopes to chain; the descending tie-break prevents it.
- Using
bisect_right: nesting must be strictly increasing, so the lower bound is required. - Sorting by area or width alone: both dimensions must strictly increase.
- Using the O(n^2) LIS: with up to 10^5 envelopes it times out.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.