Cracking The Coding Interview Together – Problem 8.13: Stack of Boxes

Have you ever tried to organize a cluttered garage, stacking storage bins of varying dimensions on top of each other? Naturally, you quickly realize a physical constraint: you cannot place a larger bin on top of a smaller one unless it fits cleanly within its footprint, but here, the rules are even stricter. In our software engineering interview journey today, we are tackling a classic spatial optimization challenge. We need to maximize the height of a stack of three-dimensional boxes under strict inclusion criteria. If we are not careful with how we order and evaluate our choices, we can easily fall into an exponential trap of redundant calculations. Let us roll up our sleeves and build an optimal solution together.

Problem Statement

We are given a stack of n boxes where each box has a specific width (w), height (h), and depth (d). The core operational goal is to compute the maximum possible height of a valid stack of these boxes. However, we must adhere to a strict invariant: a box can only be placed on top of another box if it is strictly smaller in every dimension—width, height, and depth—than the box immediately below it. Crucially, the boxes cannot be rotated; their orientation is fixed.

Analyze the Problem Together

Let us break down the constraints. At first glance, this problem shares a striking resemblance to the classic Longest Increasing Subsequence (LIS) problem, but extended into three dimensions with custom objects. We have a set of boxes, and we want to find a subset that can be ordered such that each subsequent box is strictly smaller than the one below it, while maximizing the sum of their heights.

What is the "Aha!" conflict here? If we simply try to generate every possible permutation of the boxes, our time complexity will skyrocket to O(n!), which is completely unusable for anything more than a handful of boxes. Instead, we must realize that sorting the boxes by one of their dimensions (say, height or width) dramatically simplifies our search space. Once sorted, we can evaluate sub-problems recursively, caching our results to avoid redundant work.

Questions for the Interviewer

Before jumping into code, a seasoned engineer always clarifies edge cases and assumptions by asking:

• Can any of the dimensions (width, height, or depth) be negative or zero? (We assume positive integers for valid physical dimensions).
• What should we return if the input list of boxes is empty or null? (An obvious return value of 0).
• Are we guaranteed that all box dimensions are distinct, or can multiple boxes share identical dimensions?
• Is there an upper bound on n that would dictate whether an O(n^2) dynamic programming approach is acceptable?

Think About the Solution

To design our solution, we will adopt a top-down dynamic programming approach with memoization. First, we define a Box class to encapsulate our dimensions. Next, we sort our collection of boxes in descending order based on one dimension, such as height. Sorting ensures that when we iterate through our boxes, any valid box that can be placed on top of our current base box must appear later in the sorted array.

For each box in our sorted list, we have a choice: we can either use it as the base of a stack and recursively find the tallest valid stack we can build using the remaining valid boxes, or we can skip it. By memoizing the maximum height achievable starting from any given box index (with a specific bottom box constraint), we eliminate overlapping subproblems entirely.

Write Code and Explain

Here is the production-ready Java implementation for the Stack of Boxes problem:

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

class Box implements Comparable<Box> {
    int width;
    int height;
    int depth;

    public Box(int width, int height, int depth) {
        this.width = width;
        this.height = height;
        this.depth = depth;
    }

    // Check if this box can be strictly on top of another box
    public boolean canBeAbove(Box other) {
        if (other == null) return false;
        return this.width < other.width &&
               this.height < other.height &&
               this.depth < other.depth;
    }

    @Override
    public int compareTo(Box other) {
        // Sort descending by height
        return Integer.compare(other.height, this.height);
    }
}

public class BoxStacker {

    public static int maxHeight(List<Box> boxes) {
        if (boxes == null || boxes.isEmpty()) {
            return 0;
        }

        // Sort boxes in descending order of height
        Collections.sort(boxes);

        int maxHeight = 0;
        int[] memo = new int[boxes.size()];

        for (int i = 0; i < boxes.size(); i++) {
            maxHeight = Math.max(maxHeight, maxHeightHelper(boxes, i, memo));
        }

        return maxHeight;
    }

    private static int maxHeightHelper(List<Box> boxes, int bottomIndex, int[] memo) {
        if (memo[bottomIndex] > 0) {
            return memo[bottomIndex];
        }

        Box bottomBox = boxes.get(bottomIndex);
        int maxStackHeight = 0;

        for (int i = bottomIndex + 1; i < boxes.size(); i++) {
            if (boxes.get(i).canBeAbove(bottomBox)) {
                maxStackHeight = Math.max(maxStackHeight, maxHeightHelper(boxes, i, memo));
            }
        }

        maxStackHeight += bottomBox.height;
        memo[bottomIndex] = maxStackHeight;
        return maxStackHeight;
    }
}

Let us walk through this code step-by-step. We begin by defining the Box class, implementing Comparable to sort boxes descending by their height. The canBeAbove method enforces our strict inclusion criteria. In the maxHeight method, we initialize a memoization array to store the maximum stack height possible with each box serving as the bottom-most element. The recursive helper function checks if we have already computed the answer for a given bottom box; if not, it iterates through all subsequent boxes, recursively finding valid supporting stacks, adds the current box's height, and stores the result in our memo table.

Time & Space Complexity

Let us analyze the computational resources required for our approach:

• Time Complexity: Sorting the boxes takes O(n log n) time. Our dynamic programming routine evaluates each box and checks valid transitions against remaining boxes, resulting in an O(n^2) time complexity in the worst case due to memoization preventing redundant recursive branches.
• Space Complexity: The recursion call stack and our memoization array both require O(n) auxiliary space. Additionally, storing the sorted list of boxes takes O(n) space, keeping our overall memory footprint linear.

Why This Problem Matters (The Senior Perspective)

As senior engineers, we encounter variations of this problem across various domains—ranging from cloud resource bin-packing and container allocation to database indexing hierarchies. Recognizing that a complex multi-variable optimization problem can be reduced to a modified Longest Increasing Subsequence through strategic sorting is a hallmark of strong algorithmic design. Moreover, understanding how to apply memoization prevents performance bottlenecks when scaling our systems to process large datasets.

Final Thoughts

Mastering dynamic programming requires practice and an eye for identifying overlapping subproblems. By breaking down the constraints, sorting intentionally, and leveraging memoization, we transformed an exponential brute-force problem into an elegant, efficient solution. Keep experimenting with different variations, such as allowing box rotations, to further test your understanding. Happy coding, and see you in the next tutorial!