# Russian doll envelops

Interview question from the interwebz

You have a set of envelopes of different widths and heights. One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope. What is the maximum number of envelopes can you russian doll?

My implementation:

# assuming no dups
def max_russian_doll(enve):
if not enve: return 0
enve.sort()
max_global = 1
for j in xrange(len(enve) - 1):
max_local = 1
for i in xrange(j, len(enve) - 1):
if enve[i][1] < enve[i + 1][1] and enve[i][0] != enve[i + 1][0]: # @comment
max_local += 1
max_global = max(max_global, max_local)
return max_global

envelopes = [(4,5), (6,7), (2,3)]
max_russian_doll(envelopes)


obviously this is $O(n^2)$. Right now I'm trying to figure out faster solution. Any tips?

• envelopes.sort() looks out-of-place.... should that be enve.sort()? – rolfl Jun 23 '14 at 17:02
• do you have some more test cases ? – sundar nataraj Jun 24 '14 at 5:41
• @rolfl yes! I just had the text. I made up the test case. My first observation is that we repeat some comparisons. Can we cache that? Dynamic programming? – Lukasz Madon Jun 24 '14 at 10:37
• Your algorithm does not handle the case where the first elements of the tuples are same: max_russian_doll([(4,5), (4,6), (6,7), (2,3)] ) is 4. But (4,5) and (4,6) can't be both counted by the definition. – abuzittin gillifirca Jun 24 '14 at 10:56
• Now, if you had somehow handled the repeating widths, the question turns to a Longest increasing subsequence after sorting according to widths, which has O(n log n) complexity, which you should probably shoot for. – abuzittin gillifirca Jun 24 '14 at 11:00

Using LIS from Wikipedia.

def max_russian_doll(seq):
if not seq: return 0
seq.sort()
M = [0] * (len(seq) + 1)
L = 1
for i in xrange(len(seq)):
lo = 1
hi = L
while lo <= hi:
mid = (hi - lo)/2 + lo
if seq[M[mid]][1] < seq[i][1] and seq[M[mid]][0] < seq[i][0]:
lo = mid + 1
else:
hi = mid - 1
newL = lo
if newL > L:
M[newL] = i
L = newL
return L

print max_russian_doll([]) == 0
print max_russian_doll([(1,1)]) == 1
print max_russian_doll([(1,1), (1,1), (1,1)]) == 1
print max_russian_doll([(4,5), (4,6), (6,7), (2,3), (1,1)]) == 4 # e.g (1,1) -> (2,3) -> (4,5) -> (6,7)
print max_russian_doll([(4,5), (4,6), (6,7), (2,3), (1,1), (1,1)]) == 4
print max_russian_doll([(5,4), (6,4), (6,7), (2,3)]) == 3

• Gives wrong result for: [(1,100),(2,200),(3,300),(4,400),(4,250),(5,300),(6,350)] – BartoszKP Jun 14 '16 at 13:12