Get height for tallest possible stack of boxes

Question

This code is meant to compute the height for the tallest stack of boxes out of a given collection of boxes. A box has width, height, and depth dimensions. The height of a stack of boxes is the sum of all of the heights of the boxes in the stack. The boxes cannot be rotated. A box can only be stacked on top of another box if its width, height, and depth are strictly smaller.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

from operator import attrgetter

class Box:
    def __init__(self, width, height, depth):
        self.width = width
        self.height = height
        self.depth = depth

    def smaller_than(self, other_box):
        return (self.width < other_box.width and
                self.height < other_box.height and
                self.depth < other_box.depth) 

def tallest(boxes):
    boxes = sorted(boxes, reverse=True, key=attrgetter('height'))
    largest_height = 0
    for i in range(len(boxes)):
        bottom_box = boxes[i]
        total_height = bottom_box.height
        cur_top_box = bottom_box
        for j in range(i+1,len(boxes)):
            if boxes[j].smaller_than(cur_top_box):
                total_height += boxes[j].height
                cur_top_box = boxes[j]
        if total_height > largest_height:
            largest_height = total_height
    return largest_height

The question wasn't clear about how the boxes were represented or inputted. I just made them into a Box class and assumed that they were passed as a list to tallest(). If there are any better ways of representing the boxes or inputting them (especially in an interview environment) I would be happy to hear it.

I think this code has time complexity O(n^2) and space complexity O(n). Please correct me if I'm wrong. Any suggestions about how I can improve these complexities are welcome.

Answer 1

The code implements a greedy approach (to be exact, n greedy attempts): as soon as a box can be placed, it is placed. It does not necessarily give an optimal solution. For example, with the set of boxes ((height, width)):

    5, 5
    4, 1
    3, 4
    2, 3

the algorithm will only consider towers

    (5,5) (4,1)
    (4,1)
    (3,4) (2,3)
    (2,3)

but not an optimal tower

    (5,5), (3,4), (2,3)

You are right about the complexity of the algorithm, but I am afraid it is not relevant if the algorithm itself is not correct.

Answer 2

I feel that the Box class represent more an immutable state than a mutable one. As such, I suggest using collections.namedtuple as a base:

>>> Box = namedtuple('Box', 'width height depth')
>>> b = Box(1, 2, 3)
>>> b
Box(width=1, height=2, depth=3)

Now if you want to add method to that, just subclass it. You can also take advantage of the fact that the underlying data is indeed a tuple, hence iterable:

class Box(namedtuple('Box', 'width height depth')):
    def smaller_than(self, other):
        return all(dim < other_dim for dim, other_dim in zip(self, other))

And voilà.

>>> b = Box(1, 2, 3)
>>> bb = Box(2, 3, 4)
>>> b.smaller_than(bb)
True
>>> bb = Box(2, 3, 3)
>>> b.smaller_than(bb)
False