0765HardArrayDynamic ProgrammingSorting

Tallest Crate Tower

Tracked in this browser only

Trains the technique from

LeetCode 1691Maximum Height by Stacking Cuboids

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A warehouse holds n rectangular crates. crates[i] lists the three side lengths of crate i in no particular order.

A crate may be set down on any of its faces, so for each crate you are free to decide which of its three sides becomes its width, which becomes its depth and which becomes its height. Rotation is unrestricted, and each crate is oriented independently.

Once oriented, crate i may be placed directly on crate j only if all three of its measurements are no larger than crate j's: width_i <= width_j, depth_i <= depth_j and height_i <= height_j. Equal measurements are allowed.

Pick any subset of the crates and any order for them, orient each one as you like, and build a single tower where every crate rests on the one below it. Return the greatest possible total height. A tower may consist of one crate.

Examples

Example 1

Input: crates = [[1, 1, 10], [2, 2, 20], [3, 3, 30]]
Output: 60

Put the crate measuring 3 by 3 by 30 on the floor, the 2 by 2 by 20 crate on top of it and the 1 by 1 by 10 crate on top of that. Each crate's three measurements are no larger than those of the crate below, and the heights add to 60.

Example 2

Input: crates = [[2, 2, 2], [3, 3, 3], [100, 1, 1]]
Output: 100

Set the crate with sides 100, 1 and 1 down on its 1 by 1 face so that it stands 100 tall. That single crate is a tower of height 100.

Example 3

Input: crates = [[41, 28, 52]]
Output: 52

There is one crate. Resting it on the face measuring 41 by 28 leaves 52 standing vertically, so the tower is 52 high.

Constraints

1 <= crates.length <= 100
crates[i].length == 3
1 <= crates[i][j] <= 100

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def tallest_stack(crates: list[list[int]]) -> int:

Java

public int tallestStack(int[][] crates)

The intended approach

Time O(n^2) for n crates, after an O(n log n) sort.Space O(n) for the normalised list and the table.

Since a crate may be turned freely, replace each crate's three sides by the same three numbers in ascending order; the placement test then only has to compare like with like, and the last of the three is the height used. Sort the normalised crates, which guarantees that any crate able to sit under another appears earlier in the list, and fill a table where the entry for crate `i` is the tallest tower with crate `i` on the floor: its own height plus the best earlier entry whose three measurements are all no larger. The answer is the largest table entry.

Pythonentry point: tallest_stack

def tallest_stack(crates):
    # Time O(n^2) after an O(n log n) sort, space O(n).
    boxes = sorted(sorted(c) for c in crates)
    n = len(boxes)
    dp = [b[2] for b in boxes]
    best = 0
    for i in range(n):
        bi = boxes[i]
        for j in range(i):
            bj = boxes[j]
            if bj[0] <= bi[0] and bj[1] <= bi[1] and bj[2] <= bi[2]:
                cand = dp[j] + bi[2]
                if cand > dp[i]:
                    dp[i] = cand
        if dp[i] > best:
            best = dp[i]
    return best

The obvious version

Search every tower directly. State is the set of crates already used together with the measurements of the crate currently on top; from there try each unused crate in each of its up to six orientations and keep whichever gives the greatest added height. Results are memoised on that state. Exponential in the crate count, so only usable on tiny warehouses.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_tallest_stack(crates):
    n = len(crates)
    orient = []
    for c in crates:
        a, b, d = c
        opts = set()
        for p in ((a, b, d), (a, d, b), (b, a, d), (b, d, a), (d, a, b), (d, b, a)):
            opts.add(p)
        orient.append(sorted(opts))
    memo = {}

    def best(mask, top):
        key = (mask, top)
        if key in memo:
            return memo[key]
        out = 0
        for i in range(n):
            if mask & (1 << i):
                continue
            for w, l, h in orient[i]:
                if w <= top[0] and l <= top[1] and h <= top[2]:
                    cand = h + best(mask | (1 << i), (w, l, h))
                    if cand > out:
                        out = cand
        memo[key] = out
        return out

    return best(0, (101, 101, 101))

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in