# O(Nlog(N)) python solution explained

• Sort the envelopes first by increasing width. For each block of same-width envelopes, sort by decreasing height.

Then find the longest increasing subsequence of heights.

Since each same-width subarray is non-increasing in height, we can never pick more than one height within each width (otherwise heights would be non-increasing)

Thus, the resulting longest increasing heights subsequence is also increasing in width.

Example:

input

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

sort by increasing widths, then decreasing heights:

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

Get the heights:

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

Find the length longest increasing subsequence:

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

(Note that we could not have picked more than one evelope with width 6)

``````class Solution(object):
def maxEnvelopes(self, envs):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
# sort first by increasing width
# within each subarray of same-width envelopes
# sort by decreasing height
envs.sort(key=lambda (w,h): (w,-h))

# now find the length of the longest increasing subsequence of heights.
# Since each same-width block was sorted non-increasing,
# we can only pick at most one height within each block
# otherwise, the sequence would be non-increasing
tails=[]
for (w,h) in envs:
idx=bisect.bisect_left(tails, h)
if idx==len(tails):
tails.append(h)
elif idx==0 or tails[idx-1]<h:
tails[idx]=h
return len(tails)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.