- 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)

1 | Example: |

#### java

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

Java NLogN Solution with Explanation

- Sort the array. Ascend on width and descend on height if width are same.
- 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]
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24public int maxEnvelopes(int[][] envelopes) {

if(envelopes == null || envelopes.length == 0

|| envelopes[0] == null || envelopes[0].length != 2)

return 0;

Arrays.sort(envelopes, new Comparator<int[]>(){

public int compare(int[] arr1, int[] arr2){

if(arr1[0] == arr2[0])

return arr2[1] - arr1[1];

else

return arr1[0] - arr2[0];

}

});

int dp[] = new int[envelopes.length];

int len = 0;

for(int[] envelope : envelopes){

int index = Arrays.binarySearch(dp, 0, len, envelope[1]);

if(index < 0)

index = -(index + 1);

dp[index] = envelope[1];

if(index == len)

len++;

}

return len;

}

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

clever solution, here is my C++ version

1 | class Solution { |

What a concise and comprehensive explanation!

Here is my Python code following your thought:

1 | from bisect import bisect_left |

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

Simple DP solution

1 | public int maxEnvelopes(int[][] envelopes) { |

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

Short and simple Java solution (15 lines)

1 | public int maxEnvelopes(int[][] envelopes) { |

#### 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)

1 | bool cmp (pair<int, int> i, pair<int, int> j) { |

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

1 | ///O(nlogn) |

1 | ///DP |

#### 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)

1 | def maxEnvelopes(self, envelopes): |

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

1 | class Solution(object): |

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].