> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Russian Doll Envelopes Python Solution

> Tested Python solution for LeetCode 354 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 354, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Binary Search](/catalog/topics/binary-search), [Dynamic Programming](/catalog/topics/dynamic-programming), [Sorting](/catalog/topics/sorting), Longest Increasing Subsequence. [View on LeetCode](https://leetcode.com/problems/russian-doll-envelopes/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 354   # by problem number
lcpy gen -s russian_doll_envelopes   # by problem name
```

## Problem

You are given a 2D array of integers `envelopes` where `envelopes[i] = [wi, hi]` represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope's width and height.

Return *the maximum number of envelopes you can Russian doll (i.e., put one inside the other)*.

**Note:** You cannot rotate an envelope.

### Examples

```
Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).
```

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

### Constraints

* 1 \<= envelopes.length \<= 10\<sup>5\</sup>
* `envelopes[i].length == 2`
* 1 \<= w\<sub>i\</sub>, h\<sub>i\</sub> \<= 10\<sup>5\</sup>

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/russian_doll_envelopes/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/russian_doll_envelopes/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from bisect import bisect_left


class Solution:
    # Sort widths ascending (heights descending within equal widths), then the
    # answer is the longest strictly increasing subsequence of heights: patience
    # sorting with bisect_left keeps equal heights from chaining.
    # Time: O(n log n)
    # Space: O(n)
    def max_envelopes(self, envelopes: list[list[int]]) -> int:
        tails: list[int] = []
        for _, height in sorted(envelopes, key=lambda e: (e[0], -e[1])):
            index = bisect_left(tails, height)
            if index == len(tails):
                tails.append(height)
            else:
                tails[index] = height
        return len(tails)
```

## Complexity

| Time | Space |
| - | - |
| O(n log n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.