Unique Binary Search Trees

From LeetCode

problem description / no solution provided

Solution in Python3

class Solution:
    def numTrees(self, n: int) -> int:
        nums = [1]   # One unique empty tree
        for i in range(1, n + 1):
            num = 0
            for j in range(i):
                num += nums[j] * nums[i - j - 1]
            nums.append(num)
        return nums[-1]     

I am lucky to get

Runtime: 36 ms, faster than 70.82% of Python3 online submissions for Unique Binary Search Trees.

Time Complexity

\(O(n^2\log^2(n))\).

Note: Assume multiplication takes \(\log^2{n}\).