Russian Doll Envelopes - Dynamic Programming / Dynamic number of subproblems

Problems
1

https://algo.monster/problems/russian_doll_envelopes

2

don’t even need to sort by sum actually. we just need to sort by width. at first sorting by width is natural, but then we run into the problem of what if two envelopes have the sum width but differing heights (which would be in ascending as well since the width causes a tiebreaker). we don’t want to count envelopes[j] (if j < i) just because envelopes[i][1] > envelopes[i][1] – we need both width and height to be larger – so let’s just do an extra check to make sure the width is larger too! thus, technically its if envelopes[i][1] > envelopes[j][1] and envelopes[i][0] > envelopes[j][0] though you could rewrite it width the width check first for it to look better, but the logic is that we are looking for a LIS in the height after the initial sort, and then need to do an extra check for the width not matching!

3

This solution will time out!

4

Can you elaborate?

5

You can sort by both width and height:
sorted(envelopes, key=lambda x: (x[0], x[1]))

6

Solution times out on leetcode… at least when i checked

7

def binarysearch(arr, target):
l = 0
r = len(arr) - 1
bi = -1

while l <= r:
    m = (l+r)//2
    mid = arr[m]

    if mid == target:
        bi = m
        break
    elif mid > target:
        bi = m
        r = m - 1
    elif mid < target:
        l = m + 1

arr[bi] = target

def max_layers(envelopes: List[List[int]]) → int:

envelopes.sort(key=lambda x: (x[0],-x[1]))

dp = []
for e in envelopes:
    if not dp:
        dp.append(e[1])
        continue
    
    last = dp[-1]
    if last < e[1]:
        dp.append(e[1])
    else:
        binarysearch(dp, e[1])
    
        
return len(dp)
8

That’s the default behavior, you don’t need the lambda.

9

Mods should include the binary search solution to solve this problem which is detailed here:
https://labuladong.gitbook.io/algo-en/iii.-algorithmic-thinking/russiandollenvelopes