LeetCode 354: Russian Doll Envelopes Solution in Python – A Step-by-Step Guide

What Is LeetCode 354: Russian Doll Envelopes?

In LeetCode 354: Russian Doll Envelopes, you’re given an array envelopes, where envelopes[i] = [w_i, h_i] represents the width and height of the i-th envelope. Your task is to find the maximum number of envelopes that can be nested, where an envelope can fit inside another only if both its width and height are strictly less than the outer envelope’s dimensions (w_i < w_j and h_i < h_j). For example, with envelopes = [[5,4], [6,4], [6,7], [2,3]], the maximum nesting is 3 (e.g., [2,3] → [5,4] → [6,7]).

Problem Statement

• Input: An array envelopes of integer pairs [w_i, h_i].
• Output: An integer—the maximum number of envelopes that can be nested.
• Rules:
• Envelope i fits in j if w_i < w_j and h_i < h_j.
• Return the length of the longest nesting sequence.

Constraints

• 1 <= envelopes.length <= 10⁵
• envelopes[i].length == 2
• 1 <= w_i, h_i <= 10⁵

Examples

• Input: envelopes = [[5,4], [6,4], [6,7], [2,3]]
• Output: 3
• Why: [2,3] → [5,4] → [6,7] (or [2,3] → [6,4] → [6,7]).
• Input: envelopes = [[1,1], [1,1], [1,1]]
• Output: 1
• Why: All identical, only one can be used.
• Input: envelopes = [[4,5], [4,6], [6,7], [2,3], [1,1]]
• Output: 4
• Why: [1,1] → [2,3] → [4,5] → [6,7].

Understanding the Problem: Nesting the Envelopes

To solve LeetCode 354: Russian Doll Envelopes in Python, we need to find the longest sequence of envelopes where each fits inside the next, based on strict width and height comparisons. This is a 2D version of the Longest Increasing Subsequence (LIS) problem. A naive approach—trying all subsequences—would take O(2^n) time, which is impractical for 10⁵ envelopes. Instead, we’ll optimize with:

• Best Solution (DP with Binary Search): O(n log n) time, O(n) space—fast and efficient.
• Alternative Solution (Standard DP): O(n²) time, O(n) space—simpler but slower.

Let’s dive into the Best Solution—DP with binary search—and break it down step-by-step.

Best Solution: Dynamic Programming with Binary Search

Why This Is the Best Solution

The DP with binary search approach is the top choice because it’s highly efficient—O(n log n) time and O(n) space—combining sorting with a clever LIS optimization. It sorts envelopes by width and uses binary search to maintain a list of the smallest heights that can extend the sequence, ensuring maximum length. It’s like stacking envelopes in a smart pile, quickly finding where each new one fits—optimized and elegant!

How It Works

Here’s the strategy:

• Step 1: Sort Envelopes:
• Sort by width ascending, then height descending (to handle same-width cases).
• Step 2: Build LIS on Heights:
• Use an array tails to store the smallest height ending a sequence of each length.
• For each height, binary search to find where it fits, replacing or extending tails.
• Step 3: Return Length:
• Length of tails is the maximum nesting.

Step-by-Step Example

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

• Step 1: Sort:
• Sort by width, then height descending: [[2,3], [5,4], [6,7], [6,4]].
• Step 2: LIS on Heights:
• tails = [].
• [2,3]: tails = [3].
• [5,4]: 4 > 3, tails = [3, 4].
• [6,7]: 7 > 4, tails = [3, 4, 7].
• [6,4]: 4 < 7, binary search → replace 4, tails = [3, 4, 7] (no length change).
• Step 3: Result:
• Length of tails = 3.
• Result: 3.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # Step 1: Sort by width ascending, height descending
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        # Step 2: Initialize tails array for LIS
        tails = []

        # Step 3: Process each envelope's height
        for w, h in envelopes:
            idx = bisect.bisect_left(tails, h)
            if idx == len(tails):
                tails.append(h)
            else:
                tails[idx] = h

        # Step 4: Return length of LIS
        return len(tails)

• Line 4: Sort envelopes (height descending ensures same-width envelopes don’t falsely extend sequence).
• Line 7: Initialize empty tails.
• Line 10-14: For each height:
• Line 11: Binary search for insertion point.
• Line 12-14: Append if at end, replace if found.
• Line 17: Return sequence length.
• Time Complexity: O(n log n)—sorting O(n log n), binary search O(log n) per n.
• Space Complexity: O(n)—tails array.

This is a nesting optimization marvel! (Note: bisect module required—import with import bisect.)

Alternative Solution: Standard Dynamic Programming

Why an Alternative Approach?

The standard DP approach offers a simpler, more intuitive take—O(n²) time, O(n) space—using a classic LIS method with a DP array to track the longest sequence ending at each envelope. It’s easier to understand but less efficient for large inputs. It’s like stacking envelopes one by one, checking all previous ones to see what fits—straightforward but slower!

How It Works

• Step 1: Sort by width ascending, height ascending.
• Step 2: DP array dp[i]: max nesting ending at envelope i.
• Step 3: Fill DP by comparing with previous envelopes.
• Step 4: Return max DP value.

Step-by-Step Example

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

• Step 1: Sort:
• [[2,3], [5,4], [6,4], [6,7]].
• Step 2: Initialize DP:
• dp = [1, 1, 1, 1] (each starts with 1).
• Step 3: Fill DP:
• i=0: [2,3], dp[0] = 1.
• i=1: [5,4], w>h of [2,3], dp[1] = 1 + 1 = 2.
• i=2: [6,4], w>h of [2,3], dp[2] = 1 + 1 = 2.
• i=3: [6,7], w>h of [2,3], [5,4], dp[3] = 1 + 2 = 3.
• Step 4: Result:
• max(dp) = 3.
• Result: 3.

Code for DP Approach

Copy codeclass Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # Step 1: Sort by width and height ascending
        envelopes.sort(key=lambda x: (x[0], x[1]))

        # Step 2: Initialize DP array
        n = len(envelopes)
        dp = [1] * n

        # Step 3: Fill DP
        for i in range(1, n):
            for j in range(i):
                if envelopes[i][0] > envelopes[j][0] and envelopes[i][1] > envelopes[j][1]:
                    dp[i] = max(dp[i], dp[j] + 1)

        # Step 4: Return max
        return max(dp)

• Line 4: Sort envelopes.
• Line 7-8: Each envelope starts with length 1.
• Line 11-14: Compare with previous envelopes.
• Line 17: Return longest sequence.
• Time Complexity: O(n²)—n comparisons per n.
• Space Complexity: O(n)—DP array.

It’s a classic nesting tracker!

Comparing the Two Solutions

• DP with Binary Search (Best):
• Pros: O(n log n) time, O(n) space, fast and scalable.
• Cons: Requires binary search understanding.
• Standard DP (Alternative):
• Pros: O(n²) time, O(n) space, simpler logic.
• Cons: Slower for large n.

Binary search wins for efficiency.

Additional Examples and Edge Cases

• [[1,1]]: 1.
• [[1,2], [2,3], [3,1]]: 2.
• [[2,1], [2,2]]: 1.

Both handle these perfectly.

Complexity Breakdown

• Binary Search: Time O(n log n), Space O(n).
• Standard DP: Time O(n²), Space O(n).

Binary search’s speed shines.

Key Takeaways

• Binary Search: Sort and search smart!
• Standard DP: Compare all pairs!
• Nesting: 2D LIS twist.
• Python Tip: Sorting simplifies—see [Python Basics](/python/basics).

Final Thoughts: Stack the Dolls

LeetCode 354: Russian Doll Envelopes in Python is a nesting challenge with depth. The binary search DP stacks efficiently, while standard DP offers clarity. Want more sequence fun? Try LeetCode 300: Longest Increasing Subsequence or LeetCode 1143: Longest Common Subsequence. Ready to nest? Head to Solve LeetCode 354 on LeetCode and stack those envelopes today!