This is an optimization problem. We can frame it as a search problem and do DP.
An intuitive thing to do first is to sort by area. Because an envelop with a smaller area cannot Russian Roll with a bigger area.
A dependency graph can be formed with a conditional to check if each edge is Russian Doll.
Memoized Search
# step 1 sort by area
# step 2 search from top down
# base case is the leaf node
class Solution:
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
sorted_elps = sorted(envelopes, key=lambda e: e[0] * e[1])
# index => number of dolls
memo: Dict[int, int] = {}
max_doll = 0
for i in range(len(envelopes)):
doll_path = 1 + self.doll_search_helper(sorted_elps, i, memo)
max_doll = max(max_doll, doll_path)
return max_doll
def can_fit(self, small_envelope: List[int], big_envelope: List[int]) -> bool:
return big_envelope[0] > small_envelope[0] and big_envelope[1] > small_envelope[1]
def doll_search_helper(
self,
envelopes: List[List[int]],
index: int,
memo: Dict[int, int]
) -> int:
# base case
if index in memo:
return memo[index]
# divide
max_doll = 0
for i in range(index + 1, len(envelopes)):
if self.can_fit(envelopes[index], envelopes[i]):
doll_path = 1 + self.doll_search_helper(envelopes, i, memo)
max_doll = max(max_doll, doll_path)
memo[index] = max_doll
return max_doll
DP
# define by suffix
# dp[i] = maximum number of doll envelops from envelops[i:]
# solve by suffix
# for j from i+1 to n-1
# dp[i] = max(dp[i], 1 + dp[j])
# init
# dp[n-1] = 1
# topo order
# for i from n-2 to 0
# final answer
# max from dp[i] i from 0 to n-1
class Solution:
def can_fit(self, se: List[int], be: List[int]) -> bool:
return be[0] > se[0] and be[1] > se[1]
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
sorted_elps = sorted(envelopes, key=lambda e: e[0] * e[1])
n = len(sorted_elps)
# init
dp: List[int] = [1 for _ in range(n)]
# topo order
for i in range(n-2, -1, -1):
for j in range(i+1, n):
if self.can_fit(sorted_elps[i], sorted_elps[j]):
if 1 + dp[j] > dp[i]:
dp[i] = 1 + dp[j]
max_doll = 0
for doll in dp:
if doll > max_doll:
max_doll = doll
# final answer
return max_doll
Time O(n^2) Space O(n)
Greedy Approach
The DP solution can only pass 81 / 87 test cases. For input size over 5000, the run time between n^2 and nlogn will be quite significant (~1000x).
