# LeetCode 354: Russian Doll Envelopes

## Problem Restatement

We are given a list of envelopes.

Each envelope has:

```python
[width, height]
```

One envelope can fit inside another only if both dimensions are strictly smaller.

That means:

```python
w1 < w2
and
h1 < h2
```

We want the maximum number of envelopes we can nest inside each other.

This is called the Russian doll property.

We may reorder the envelopes in any way.

## Input and Output

| Item | Meaning |
|---|---|
| Input | List of envelopes `[[w, h], ...]` |
| Output | Maximum nesting length |
| Rule | Both width and height must be strictly increasing |

Example function shape:

```python
def maxEnvelopes(envelopes: list[list[int]]) -> int:
    ...
```

## Examples

Example 1:

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

One valid nesting chain is:

```python
[2,3] -> [5,4] -> [6,7]
```

Length:

```python
3
```

So the answer is:

```python
3
```

Example 2:

```python
envelopes = [[1,1],[1,1],[1,1]]
```

No envelope can fit into another because equal dimensions are not allowed.

So the answer is:

```python
1
```

## First Thought: Dynamic Programming

A direct idea is:

1. Sort the envelopes.
2. Use DP similar to longest increasing subsequence.

Let:

```python
dp[i]
```

mean:

```text
maximum nesting chain ending at envelope i
```

Transition:

```python
if envelopes[j] fits into envelopes[i]:
    dp[i] = max(dp[i], dp[j] + 1)
```

This works.

But the complexity is:

```python
O(n^2)
```

For large input, we need something faster.

## Key Insight

The problem becomes much simpler after sorting carefully.

Suppose we sort by:

1. Width ascending
2. Height descending when widths are equal

Example:

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

becomes:

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

Actually after applying the correct rule:

```python
sorted(envelopes, key=lambda x: (x[0], -x[1]))
```

the result is:

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

Now focus only on heights:

```python
[3, 4, 7, 4]
```

The problem becomes:

```text
find the longest strictly increasing subsequence
```

Why does descending height for equal widths matter?

Suppose we had:

```python
[[6,4],[6,7]]
```

If heights were ascending, LIS on heights would incorrectly allow:

```python
4 -> 7
```

But widths are equal, so nesting is illegal.

Sorting equal widths by descending height prevents this mistake.

After sorting:

```python
[[6,7],[6,4]]
```

Now heights are:

```python
[7,4]
```

which cannot form an increasing subsequence.

This converts the 2D problem into a 1D LIS problem.

## Algorithm

Step 1:

Sort envelopes by:

```python
(width ascending, height descending)
```

Step 2:

Extract all heights.

Step 3:

Compute LIS on heights.

Use the standard patience sorting method.

Maintain:

```python
tails
```

where:

```text
tails[i] = smallest possible tail of an increasing subsequence of length i + 1
```

For every height:

1. Binary search its insertion position in `tails`
2. Replace that position
3. If the height is larger than all tails, append it

The length of `tails` is the answer.

## Correctness

After sorting, widths are non-decreasing.

For envelopes with equal widths, heights are sorted in descending order.

Therefore, any increasing subsequence in heights cannot contain two envelopes with the same width. If two equal-width envelopes appeared in the subsequence, their heights would decrease rather than increase.

So every strictly increasing subsequence of heights corresponds to a valid sequence where both width and height increase strictly.

Conversely, every valid nesting sequence must also have strictly increasing heights after sorting, so it forms an increasing subsequence in the height array.

Therefore, the problem reduces exactly to finding the LIS of heights.

The patience sorting LIS algorithm maintains:

```text
tails[k]
```

as the minimum possible ending value of an increasing subsequence of length `k + 1`.

Replacing larger tails with smaller ones preserves all achievable subsequence lengths while keeping future extension possibilities as flexible as possible.

Therefore, the final length of `tails` equals the maximum valid nesting depth.

## Complexity

Let `n` be the number of envelopes.

| Operation | Time | Space |
|---|---:|---:|
| Sorting | `O(n log n)` | `O(n)` depending on implementation |
| LIS | `O(n log n)` | `O(n)` |
| Total | `O(n log n)` | `O(n)` |

The binary search inside LIS gives logarithmic updates.

## Implementation

```python
from bisect import bisect_left

class Solution:
    def maxEnvelopes(self, envelopes: list[list[int]]) -> int:
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        tails = []

        for _, height in envelopes:
            pos = bisect_left(tails, height)

            if pos == len(tails):
                tails.append(height)
            else:
                tails[pos] = height

        return len(tails)
```

## Code Explanation

First we sort:

```python
envelopes.sort(key=lambda x: (x[0], -x[1]))
```

Widths increase normally.

Equal widths use descending heights.

Then we process heights only:

```python
for _, height in envelopes:
```

The `tails` array stores the smallest ending height for every subsequence length.

Suppose:

```python
tails = [3, 5, 8]
```

This means:

| Length | Smallest tail |
|---|---|
| 1 | 3 |
| 2 | 5 |
| 3 | 8 |

Now insert height `6`.

Binary search gives:

```python
pos = 2
```

because `6` should replace `8`.

New tails:

```python
[3, 5, 6]
```

This is better because a smaller tail is easier to extend later.

If the new height is larger than every tail:

```python
tails.append(height)
```

which increases the LIS length.

Finally:

```python
return len(tails)
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxEnvelopes([[5,4],[6,4],[6,7],[2,3]]) == 3

    assert s.maxEnvelopes([[1,1],[1,1],[1,1]]) == 1

    assert s.maxEnvelopes([[1,1],[2,2],[3,3],[4,4]]) == 4

    assert s.maxEnvelopes([[4,5],[4,6],[6,7],[2,3],[1,1]]) == 4

    assert s.maxEnvelopes([[2,3],[5,4],[6,4],[6,7]]) == 3

    assert s.maxEnvelopes([[30,50],[12,2],[3,4],[12,15]]) == 3

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Basic nesting chain |
| All equal | Strict inequality required |
| Fully increasing | Maximum possible chain |
| Equal widths | Checks descending-height sorting trick |
| Mixed ordering | Confirms sorting correctness |
| Random dimensions | General correctness check |