Python solution based on LIS

• It's a problem based on LIS.
DP solution for LIS is N^2 which will TLE here.
Using Binary Search approach will get accepted.

https://leetcode.com/problems/longest-increasing-subsequence/

``````def maxEnvelopes(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
if not envelopes:
return 0

l = len(envelopes)
if l == 1:
return 1

envelopes.sort(
cmp = lambda x, y: x[0] - y[0] if x[0] != y[0] else y[1] - x[1])
# sort the envelopes by width because they need to be inorder before consider the heigths or versa

width = []
for i in envelopes:
width.append(i[1])

res = self.longestSubsequence(width)
# the problem became LIS after sort(width)

return res

def longestSubsequence(self, nums):
"""
return type: int (number of longest subsequence)
"""
if not nums:
return 0
l = len(nums)
res = []

for num in nums:
pos = self.binarySearch(num, res)
if pos >= len(res):
res.append(num)
else:
res[pos] = num

return len(res)

def binarySearch(self, target, nums):
"""
return type: int (ceiling of the insert position)
"""
if not nums:
return 0

l = len(nums)
start = 0
end = l - 1

while start <= end:
half = start + (end - start) // 2
if nums[half] == target:
return half
elif nums[half] < target:
start = half + 1
else:
end = half - 1

return start
``````

'''

• Wow, nice, I learned a beautiful solution from your post.
We can use bisect module to make the code concise.

``````class Solution(object):
def maxEnvelopes(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
if not envelopes:
return 0
envelopes.sort(key=lambda c:(c[0],-c[1]))
return self.longestSubsequece(list(map(lambda c: c[1], envelopes)))

def longestSubsequece(self, arr):
q = []
for i in arr:
pos = bisect.bisect_left(q, i)
if len(q) == pos:
q.append(i)
else:
q[pos] = i
return len(q)
``````

Almostly same as yours.

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