⚡Flashcard Drill➔
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

  1. Sort by width ascending; for equal widths, sort height in descending order.
  2. The problem then becomes a longest strictly increasing subsequence on the heights.
  3. The descending tie-break ensures two envelopes of equal width can never both be selected, since their heights appear in decreasing order.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems