How do you solve Maximum Height by Stacking Cuboids on LeetCode?

Maximum Height by Stacking Cuboids (LeetCode #1691) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Sorting cuboids helps in reducing the complexity of checking stackability.

What is the time complexity of Maximum Height by Stacking Cuboids ?

The optimal solution for Maximum Height by Stacking Cuboids runs in O(n²) time and uses O(n) space. The time complexity is O(n²) due to the nested loop for checking stackable cuboids, while the space complexity is O(n) for the DP array.

What is the brute force solution for Maximum Height by Stacking Cuboids ?

The brute force approach for Maximum Height by Stacking Cuboids is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking all possible combinations of cuboids to see which can be stacked on top of each other. This method is straightforward but inefficient due to its combinatorial nature. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Maximum Height by Stacking Cuboids ?

Maximum Height by Stacking Cuboids uses the following concepts: Array, Dynamic Programming, Sorting. The recommended patterns to study are: Dynamic Programming, Sorting.

What are the interview tips for Maximum Height by Stacking Cuboids ?

Always clarify the problem constraints and requirements before diving into coding. Discuss your thought process and approach with the interviewer to show your understanding. Practice explaining your code and logic clearly, as communication is key in interviews.

What are common mistakes when solving Maximum Height by Stacking Cuboids ?

Not considering all rotations of cuboids before stacking. Failing to sort cuboids correctly, which can lead to incorrect stackability checks.

#1691

Maximum Height by Stacking Cuboids

Hard

ArrayDynamic ProgrammingSortingDynamic ProgrammingSorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

The optimal solution involves sorting the cuboids and using dynamic programming to build the maximum height incrementally. By sorting, we ensure that we only need to check each cuboid against the previous ones, significantly reducing the complexity.

⚙️

Algorithm

4 steps

1Step 1: Sort the cuboids by width, length, and height in descending order.
2Step 2: Initialize a DP array where dp[i] represents the maximum height achievable with the i-th cuboid at the base.
3Step 3: For each cuboid, check all previous cuboids to see if they can be stacked on top, updating the DP array accordingly.
4Step 4: The result will be the maximum value in the DP array.

solution.py12 lines

1def maxHeight(cuboids):
2    # Sort cuboids by width, length, height
3    cuboids = [sorted(c) for c in cuboids]
4    cuboids.sort(reverse=True)
5    n = len(cuboids)
6    dp = [0] * n
7    for i in range(n):
8        dp[i] = cuboids[i][2]  # Base height is the height of the cuboid itself
9        for j in range(i):
10            if (cuboids[i][0] <= cuboids[j][0] and cuboids[i][1] <= cuboids[j][1]):
11                dp[i] = max(dp[i], dp[j] + cuboids[i][2])
12    return max(dp)

ℹ

Complexity note: The time complexity is O(n²) due to the nested loop for checking stackable cuboids, while the space complexity is O(n) for the DP array.

1Sorting cuboids helps in reducing the complexity of checking stackability.
2Dynamic programming allows us to build solutions incrementally, leveraging previously computed results.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.