Problem statement

https://leetcode.com/problems/maximum-height-by-stacking-cuboids/

Solution

My first solution was to sort all cuboids by sum of all dimensions: this is neccesary (but not enough) condition to stack and generate all rotations as well. Then we have O(6n) candidates and then we can apply LIS problem with total complexity O(36n^2).

In fact it can be solved in O(n^2) complexity: we can always rotate our cuboids such that they have sorted coordinates. Imagine, that we have two stacked cuboids (X1, X2, X3) and (Y1, Y2, Y3), then it can be shown that (X_min, X_mid, X_max) and (Y_min, Y_mid, Y_max) also can be stacked, but in this case sum of heights can be only increased. (Easier to show this if we put points on line and check cases).

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def maxHeight(self, C):
        D = sorted(map(sorted, C))
        
        def check(X, Y):
            return X[0] >= Y[0] and X[1] >= Y[1] and X[2] >= Y[2]
        
        @lru_cache(None)
        def dp(i):
            if i == -1: return 0
            return max([dp(j) for j in range(i) if check(D[i], D[j])] or [0]) + D[i][2]
        
        return max(dp(i) for i in range(len(D)))