Disk Stacking

Tags

Disk Stacking

Category

Dynamic Programming

Difficulty

Hard

Problem Statement

Given a list of disks where each disk is represented by [width, depth, height], stack them to maximize total height. A disk can only be placed on top of another if it is strictly smaller in all three dimensions (width, depth, and height) than the disk below it. Return the stacked disks in order from bottom to top.

Intuition

This is a variant of the Longest Increasing Subsequence (LIS) problem in three dimensions. If we sort the disks by one dimension (e.g., height), then for each disk we only need to look at previously considered disks to check if they can sit below it. The optimal stack ending at disk i is the best stack ending at some valid predecessor j plus disk i itself.

Approach

  1. Sort disks by height (ascending).
  2. Create an array heights where heights[i] is the maximum stack height ending with disk i, initialized to each disk's own height.
  3. Create a predecessors array to track which disk comes before each disk in the optimal stack.
  4. For each disk i, iterate over all previous disks j < i:
    • If disk j is strictly smaller in all three dimensions than disk i, and heights[j] + disk[i].height > heights[i], update heights[i] and record j as the predecessor of i.
  5. Find the index with the maximum value in heights.
  6. Backtrack through predecessors to build the stack.

Pseudocode

function diskStacking(disks):
    sort disks by height ascending

    heights = [disk[2] for disk in disks]    // each disk's own height
    predecessors = [-1, -1, ..., -1]          // length n

    for i from 1 to n-1:
        for j from 0 to i-1:
            if disks[j][0] < disks[i][0] and
               disks[j][1] < disks[i][1] and
               disks[j][2] < disks[i][2]:
                if heights[j] + disks[i][2] > heights[i]:
                    heights[i] = heights[j] + disks[i][2]
                    predecessors[i] = j

    maxIdx = index of max value in heights
    stack = []
    while maxIdx != -1:
        stack.append(disks[maxIdx])
        maxIdx = predecessors[maxIdx]

    return reverse(stack)

Time & Space Complexity

MeasureComplexityJustification
TimeO(n^2)For each disk, we compare against all previous disks
SpaceO(n)Arrays for heights and predecessors

Key Insights

  • Sorting by one dimension reduces the problem to a 1D LIS-style DP where only "backward" comparisons are needed.
  • Strict inequality in all three dimensions is required — not just two.
  • The choice of which dimension to sort by does not affect correctness, but sorting by height is natural since we are maximizing total height.
  • Unlike classic LIS, there is no O(n log n) optimization here because the ordering is partial (three dimensions), not total.

Edge Cases

  • Single disk: the answer is just that disk.
  • No disk can be placed on another: the tallest individual disk is the answer.
  • All disks are identical: only one disk can be in the stack.
  • Disks that match in one or two dimensions but not all three: they cannot be stacked (strict inequality required on every dimension).

Linked mentions