Fastest Solution Yet
Intuition\nGiven an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elem
# Intuition\nGiven an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.\n\nThe code works as follows:\n1. It first defines a function ```cnr()``` that calculates the combination of two numbers. This function is used later in the code to calculate the number of ways to split a range of numbers into two smaller ranges.\n\n2. It then defines two arrays, ```leng``` and ```cnt```, which store the length and count of each range of numbers, respectively.\n\n3. It then iterates through the array ```nums``` in reverse order. For each number ```p```, it calculates the length of the range of numbers to the left of ```p``` (stored in ```h```) and the length of the range of numbers to the right of ```p``` (stored in ```k```).\n\n4. It then calculates the number of ways to split the range of numbers from ```p-h``` to ```p+k``` into two smaller ranges (left sub-tree and right sub-tree). This is done by multiplying the count of the range of numbers to the left of ```p``` (stored in ```cnt[p-1]```), the count of the range of numbers to the right of ```p``` (stored in ```cnt[p+1]```), and the combination of ```h+k``` and ```h```.\n\n5. It then updates the length and count of the range of numbers from ```p-h``` to ```p+k``` to be ```h+k+1``` and ```t```, respectively.\n\n6. It repeats steps 3-5 for each number in ```nums```.\n\n7. It then returns the count of the range of numbers from ```1 to n```, which is stored in ```cnt[1]```.\n\n\n\n\n# Approach\nUse bottom-up recursion with merge interval.\n\n# Complexity\n- Time complexity:$$O(n^2)$$. This is because the code iterates through the array nums once, and for each number in the array, it calculates the length and count of the range of numbers to the left and right of the number. The space complexity of the code is O(n), because it stores the arrays leng and cnt.\n\n- Space complexity:$$O(n^2)$$.  This is because the two arrays leng and cnt both have a size of n+2, and each element in the arrays takes up constant space. Therefore, the total space complexity is O(n^2).\n\nHere is a breakdown of the space complexity of each of the two arrays:\n\n    - leng: This array stores the lengths of the intervals that have been processed so far. The size of this array is n+2 because we need to store the lengths of all intervals, including the empty interval at the beginning and end.\n    \n    - cnt: This array stores the number of ways to partition the intervals that have been processed so far. The size of this array is also n+2 because we need to store the number of ways to partition all intervals, including the empty partition at the beginning and end.\n\n\nThe total space complexity is then the sum of the space complexities of the two arrays, which is O(n^2).\n\n\n\n# Code\n```\nclass Solution:\n    def numOfWays(self, nums: List[int]) -> int:\n        mod = 1000000007\n        n = len(nums)\n\n\n        # stores the length of each range of numbers, respectively.\n        leng = [0]*(n+2) \n\n        # stores the count of each range of numbers, respectively.\n        cnt = [1]*(n+2) \n\n        # Iterate the array in reverse order\n        for p in nums[::-1]: \n            # k consecutive values larger than p (on the left) are already in BST if leng[p+1] > 0 indicates that. Length [p+1] and h are the respective integers in the right child BST of p.\n            h,k = leng[p-1],leng[p+1] \n\n            # The size of the BST rooted at p should be used to update the lengths at the rightmost and leftmost numbers in the BST (consecutive intervals). Because it won\'t be needed in the subsequent computation of length and cnt, the numbers in between (p-h, p+k) don\'t need to be updated.\n            leng[p-h]=leng[p+k]=h+k+1 \n\n            # The number of permutated arrays that can construct the BST of the left child and the right child of p is given by dp(BST rooted at p) = dp(left(p-1))*dp(right(p+1))*C(left+right,right).\n            t = (cnt[p-1]*cnt[p+1]%mod)*comb(h+k,h)%mod \n\n            # Only the cnt\'s rightmost and leftmost elements should be updated because those two numbers will be the only ones used in the next merge interval.\n            cnt[p-h]=cnt[p+k]=t \n\n            # return the number of ways to reorder nums\n        return (cnt[1]-1)%mod           \n```
['Backtracking', 'Binary Search Tree', 'Recursion', 'Combinatorics', 'Python3']