patternpythonMinor

Russian doll envelops

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

dollenvelopsrussian

Problem

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?

Solution

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

Code Snippets

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

Context

StackExchange Code Review Q#55044, answer score: 3

Revisions (0)

No revisions yet.