Maximum Height by Stacking Cuboids - Practice Coding Problems

Maximum Height by Stacking Cuboids - Problem

Given n cuboids where the dimensions of the ith cuboid is cuboids[i] = [width_i, length_i, height_i] (0-indexed).

Choose a subset of cuboids and place them on each other. You can place cuboid i on cuboid j if width_i <= width_j and length_i <= length_j and height_i <= height_j.

You can rearrange any cuboid's dimensions by rotating it to put it on another cuboid.

Return the maximum height of the stacked cuboids.

Input & Output

Example 1 — Basic Stacking

$ Input: cuboids = [[50,45,20],[95,37,53],[45,23,12]]

› Output: 190

💡 Note: After sorting dimensions: [[20,45,50],[37,53,95],[12,23,45]]. Sorted cuboids: [[12,23,45],[20,45,50],[37,53,95]]. We can stack all three: 45+50+95 = 190.

Example 2 — Subset Selection

$ Input: cuboids = [[38,25,45],[76,35,3]]

› Output: 76

💡 Note: After sorting: [[25,38,45],[3,35,76]]. We cannot stack them (25≤3 is false), so best is single cuboid with height 76.

Example 3 — Single Cuboid

$ Input: cuboids = [[7,11,17]]

› Output: 17

💡 Note: Only one cuboid, maximum height is its largest dimension after rotation: max(7,11,17) = 17.

Constraints

n == cuboids.length
1 ≤ n ≤ 100
1 ≤ width_i, length_i, height_i ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Cuboids with 3 dimensions each, can be rotated

Process

Sort and find optimal stacking arrangement

Output

Maximum achievable height of stacked cuboids

Key Takeaway

🎯 Key Insight: Sort cuboids by dimensions to transform into longest increasing subsequence problem

Asked in

a Amazon 15 G Google 12 M Microsoft 8 f Facebook 6

The key insight is to sort dimensions within each cuboid, then sort all cuboids to enable dynamic programming. This transforms the problem into a variant of the longest increasing subsequence. Best approach uses sorting + DP with Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Sort Then Dynamic Programming	O(n²)	O(n)	Sort cuboids optimally, then use DP for longest increasing subsequence
Brute Force with All Combinations	O(6ⁿ × 2ⁿ × n!)	O(6n)	Try all possible rotations and subset combinations

Sort Then Dynamic Programming — Algorithm Steps

Sort dimensions within each cuboid
Sort cuboids by their dimensions
Use DP to find maximum height stack
Each DP[i] represents max height ending at cuboid i

Visualization

Tap to expand

Step-by-Step Walkthrough

Normalize & Sort

Sort dimensions within each cuboid, then sort all cuboids

Dynamic Programming

Build maximum height ending at each position

Find Maximum

Return the highest achievable stack

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare_ints(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int compare_cuboids(const void* a, const void* b) {
    int* cuboidA = (int*)a;
    int* cuboidB = (int*)b;
    
    if (cuboidA[0] != cuboidB[0]) return cuboidA[0] - cuboidB[0];
    if (cuboidA[1] != cuboidB[1]) return cuboidA[1] - cuboidB[1];
    return cuboidA[2] - cuboidB[2];
}

int solution(int** cuboids, int cuboidsSize, int* cuboidsColSize) {
    if (cuboidsSize == 0) return 0;
    
    // Convert to 2D array for easier sorting
    int sortedCuboids[cuboidsSize][3];
    for (int i = 0; i < cuboidsSize; i++) {
        for (int j = 0; j < 3; j++) {
            sortedCuboids[i][j] = cuboids[i][j];
        }
        // Sort dimensions within each cuboid
        qsort(sortedCuboids[i], 3, sizeof(int), compare_ints);
    }
    
    // Sort cuboids
    qsort(sortedCuboids, cuboidsSize, sizeof(sortedCuboids[0]), compare_cuboids);
    
    int dp[cuboidsSize];
    
    // Initialize DP
    for (int i = 0; i < cuboidsSize; i++) {
        dp[i] = sortedCuboids[i][2];
    }
    
    // Fill DP table
    for (int i = 1; i < cuboidsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (sortedCuboids[j][0] <= sortedCuboids[i][0] &&
                sortedCuboids[j][1] <= sortedCuboids[i][1] &&
                sortedCuboids[j][2] <= sortedCuboids[i][2]) {
                int newHeight = dp[j] + sortedCuboids[i][2];
                if (newHeight > dp[i]) {
                    dp[i] = newHeight;
                }
            }
        }
    }
    
    // Find maximum
    int maxHeight = 0;
    for (int i = 0; i < cuboidsSize; i++) {
        if (dp[i] > maxHeight) {
            maxHeight = dp[i];
        }
    }
    
    return maxHeight;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int cuboids[20][3];
    int count = 0;
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            sscanf(ptr + 1, "%d,%d,%d", &cuboids[count][0], &cuboids[count][1], &cuboids[count][2]);
            count++;
        }
        ptr++;
    }
    
    int* cuboidsPtr[count];
    int colSizes[count];
    for (int i = 0; i < count; i++) {
        cuboidsPtr[i] = cuboids[i];
        colSizes[i] = 3;
    }
    
    printf("%d\n", solution(cuboidsPtr, count, colSizes));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Sorting takes O(n log n), DP comparison takes O(n²)

⚠ Quadratic Growth

Space Complexity

O(n)

DP array stores maximum height for each cuboid

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort Then Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler