• 31.9%

https://leetcode.com/problems/russian-doll-envelopes/

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

#### java

https://discuss.leetcode.com/topic/47469/java-nlogn-solution-with-explanation

Java NLogN Solution with Explanation

1. Sort the array. Ascend on width and descend on height if width are same.
2. Find the longest increasing subsequence based on height.
• Since the width is increasing, we only need to consider height.
• [3, 4] cannot contains [3, 3], so we need to put [3, 4] before [3, 3] when sorting otherwise it will be counted as an increasing number if the order is [3, 3], [3, 4]

https://discuss.leetcode.com/topic/47469/java-nlogn-solution-with-explanation/2

clever solution, here is my C++ version

What a concise and comprehensive explanation!

Here is my Python code following your thought:

https://discuss.leetcode.com/topic/47404/simple-dp-solution

Simple DP solution

https://discuss.leetcode.com/topic/47594/short-and-simple-java-solution-15-lines

Short and simple Java solution (15 lines)

#### cpp

https://discuss.leetcode.com/topic/47406/c-dp-version-time-o-n-2-space-o-n

C++ DP version, Time O(N^2) Space O(N)

https://discuss.leetcode.com/topic/47684/c-9-line-short-and-clean-o-nlogn-solution-plus-classic-o-n-2-dp-solution

C++ 9-line Short and Clean O(nlogn) solution (plus classic O(n^2) dp solution).

#### python

https://discuss.leetcode.com/topic/47443/clean-and-short-nlogn-solution

Clean and short nlogn solution

See more explanation in Longest Increasing Subsequence Size (N log N)

https://discuss.leetcode.com/topic/48160/python-o-nlogn-o-n-solution-beats-97-with-explanation

Python O(nlogn) O(n) solution, beats 97%, with explanation

The idea is to order the envelopes and then calculate the longest increasing subsequence (LISS). We first sort the envelopes by width, and we also make sure that when the width is the same, the envelope with greater height comes first. Why? This makes sure that when we calculate the LISS, we don’t have a case such as [3, 4] [3, 5] (we could increase the LISS but this would be wrong as the width is the same. It can’t happen when [3, 5] comes first in the ordering).

We could calculate the LISS using the standard DP algorithm (quadratic runtime), but we can just use the tails array method with a twist: we store the index of the tail, and we do leftmost insertion point as usual to find the right index in nlogn time. Why not rightmost? Think about the case [1, 1], [1, 1], [1, 1].