Russian Doll Envelopes

Question (LC.354)

Given a list of envelopes, find the maximum number of envelopes that one can Russian Doll.

An envelope is defined as [wi, hi] where w is the width and h is the height.

Envelope e1 can Russian Doll e2 if w1 > w2 and h1 > h2.

Examples

I: envelopes = [[5,4],[6,4],[6,7],[2,3]]
O: 3 ([2,3] -> [5,4] -> [6,7])

I: envelopes = [[1,1],[1,1],[1,1]]
O: 1

DP Approach

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.

Doll DAG

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

TBD