# Python solution with detailed explanation

• Solution

Russian Doll Envelopes https://leetcode.com/problems/russian-doll-envelopes/

• Sort along x dimension in ascending order. For equal x, sort descendng order for y.
• We do this so that we do not choose [3,4], [3,7] as a valid solution. If we make it [3,7] and [3,4], we automatically invalidate [3,4], [3,7].
• There are two ways to sort in the above way in Python using cmp method or key method. They are illustrated in the code below.
• Then apply LIS along y dimension.
``````from bisect import bisect_left
class Solution(object):
def lengthOfLIS(self, nums):
tails = []
for num in nums:
idx = bisect_left(tails, num)
if idx == len(tails):
tails.append(num)
else:
tails[idx] = num
return len(tails)

def maxEnvelopes(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
if envelopes == []:
return 0
N = len(envelopes)
# 2 ways of sorting
#        envelopes.sort(cmp=lambda x,y: x[0]-y[0] if x[0] != y[0] else y[1]-x[1])
envelopes.sort(key=lambda x:(x[0], -1*x[1]))
return self.lengthOfLIS([e[1] for e in envelopes])
``````

Dynamic Programming

• RDE[i]: Maximum RDE sequence ending at envelope i. Envelopes are sorted in ascending order.
• RDE [i] = max(RDE[j]) where j is an element of [0 to i] and (envelopes[j].length < envelopes[i].length) and (envelopes[j].width < envelopes[i].width)
``````class Solution(object):
def maxEnvelopes(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
if envelopes == []:
return 0
N = len(envelopes)
envelopes.sort(key=lambda x: x[0])
dp = [1]*len(envelopes)
max_so_far = 1
for i in range(1, N):
for j in range(i):
if (envelopes[j][0] < envelopes[i][0]) and (envelopes[j][1] < envelopes[i][1]):
dp[i] = max(dp[i], dp[j]+1)
max_so_far = max(max_so_far, dp[i])
return max_so_far
``````

Memoization

• RDE[i]: Maximum RDE sequence starting at envelope i. Envelopes are sorted in ascending order.
• RDE [i] = max(RDE[j]) where j is an element of [i+1 to N-1] and (envelopes[j].length > envelopes[i].length) and (envelopes[j].width > envelopes[i].width)
``````class Solution(object):
def helper(self, envelopes, i, k, cache):
# We are finding the longest sequence for envelope with bottom at envelope[k].
# We know that envelopes below index i cannot be candidates at all.
if k in cache:
return cache[k]
last = envelopes[k] if k >= 0 else []
cache[k] = 0
for idx in range(i, len(envelopes)):
x,y = envelopes[idx][0], envelopes[idx][1]
if not last or (x > last[0] and y > last[1]):
cache[k] = max(cache[k], self.helper(envelopes, idx+1, idx, cache) + 1)
return cache[k]

def maxEnvelopes(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
cache = {}
envelopes.sort(key = lambda x: x[0])
return self.helper(envelopes, 0, -1, cache)
``````

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