O(NlogN) asymptotically OPTIMAL solution.
O(N^2) isn\'t optimal\n\nBefore reading this, you should understand the recursive solution by reading other posts (C++, Java, doing division is a bit complicate
**O(N^2) isn\'t optimal**\n\nBefore reading this, you should understand the recursive solution by reading other posts ([C++](https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/discuss/819369/C%2B%2B-Just-using-recursion-very-Clean-and-Easy-to-understand-O(n2)), [Java](https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/discuss/819725/Java-Clean-code-uses-Yang-Hui\'sPascal\'s-Triangle-With-Explanation), [Python](https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/discuss/819282/Python-O(n2)-post-order-traversal)).\n\nOnce the BST is built, the recursion only takes O(N) steps and is optimal. However, most of the solutions here are O(N^2) because of two suboptimal steps:\n1. Naive insertion into unbalanced BST is O(N) in the worst case, so tree-building is O(N^2).\n2. Pre-computing all combination C(m,n) (aka Pascal\'s triangle) takes O(N^2)\n\nIn this post I\'ll show the optimal algorithms to the above two steps, the first one O(NlogN) and the second O(NlogP) (where P=10^9+7), making the overall complexity O(NlogN) (since P is a constant).\n\n**Building unbalanced BST with the help of balanced BST**\n\nReflecting on the BST insertion algorithm, it\'s not hard to notice that **the parent of the newly inserted number is either the next larger number or the next smaller number**.\n\nFor example, if numbers in the BST are [1,2,4,5], and the new number is 3, then regardless of the shape of the BST, 3\'s parent must be either 2 or 4.\n\nProof by contradiction is simple: if that\'s not true, there are numbers between the new number and its parent, which by the definition of BST have to be the children of the new number, violating the BST insertion algorithm that the new number is a leaf node.\n\nFurthermore, **there is always one and only one available position for insertion** between the two possibilities: "right child of the next smaller number" and "left child of the next larger number". Proof: since there are no number between "the next smaller number" and "the next larger number", either "the next larger number" is in the right subtree of "the next smaller number", or "the next smaller number" is in the left subtree of "the next larger number". In both cases, one of the two possible positions is occupied by an existing subtree.\n\nWith the observations above, we can use a balanced BST (`map` in C++ or `TreeMap` in Java) that can find "next larger/smaller number" in O(logN). With the help of a balanced BST, we can insert a number into an unbalanced BST in O(logN), thus building the whole unbalanced BST in O(NlogN). Below is my C++ code for tree-buliding:\n\n```C++\nclass Solution {\n    struct Tree{\n        Solution::Tree *l,*r;\n        int v;\n        Tree(int v):l(nullptr),r(nullptr),v(v){}\n    };\n    void insert(map<int,Tree*>& mp,int v){\n        Tree* leaf=new Tree(v);\n        auto it=mp.lower_bound(v);\n        if(it!=mp.end()&&!it->second->l){\n            it->second->l=leaf;\n        }\n        else{\n            it--;\n            it->second->r=leaf;\n        }\n        mp[v]=leaf;\n    }\npublic:\n    int numOfWays(vector<int>& nums) {\n        map<int,Tree*> mp;\n        Tree* root=new Tree(nums[0]);\n        mp[nums[0]]=root;\n        for(int i=1;i<nums.size();i++)\n            insert(mp,nums[i]);\n        // ...\n    }\n};\n```\n**Combinations formula and modular inverse**\n\nWe all know the formular for combinations, or number of ways of selecting `m` items from `n` items: `C(m,n)=n!/m!/(n-m)!`. If we pre-compute all factorials from 1 to N, we can compute any `C(m,n)` in O(1) with this formula.\n\nHowever, in modular arithmetics ("return the result modulo P"), doing division is a bit complicated. Unlike addition/subtraction/multiplication, `(a/b)%P` is not equal to `(a%P)/(b%P)`. It turns out that you need to compute `a*inv(b,P)%P` instead, where `inv(b,P)` is called the [modular inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) of b modulo P.\n\nThere are  [two algorithms modular inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Computation), both of which are O(logP) for small P that fits in a machine word. Thus, we can pre-compute all factorials and their modular inverses from 1 to N in O(NlogP), and then compute any `C(m,n)` in O(1).\n1. Extended Euclidean algorithm\n2. Exponentiation by squaring and Fermat\'s Little Theorem (`a^(P-2)=a^-1 (mod P)`)\n\nI personally prefer the second one, although it only works when P is prime. Below is the C++ code.\n```C++\ntypedef long long ll;\nconst ll P=1000000007;\nll pow(ll a,ll n){\n\tif(n==1)return a;\n\tll half=pow(a,n/2);\n\tll ret=half*half%P;\n\tif(n%2)ret=ret*a%P;\n\treturn ret;\n}\nll inv(ll a){\n\treturn pow(a,P-2);\n}\n```\n**Full code in C++**\n```C++\nclass Solution {\n    struct Tree{\n        Solution::Tree *l,*r;\n        int v;\n        Tree(int v):l(nullptr),r(nullptr),v(v){}\n    };\n    void insert(map<int,Tree*>& mp,int v){\n        Tree* leaf=new Tree(v);\n        auto it=mp.lower_bound(v);\n        if(it!=mp.end()&&!it->second->l){\n            it->second->l=leaf;\n        }\n        else{\n            it--;\n            it->second->r=leaf;\n        }\n        mp[v]=leaf;\n    }\n    typedef long long ll;\n    const ll P=1000000007;\n    vector<ll> fac,invfac;\n    ll pow(ll a,ll n){\n        if(n==1)return a;\n        ll half=pow(a,n/2);\n        ll ret=half*half%P;\n        if(n%2)ret=ret*a%P;\n        return ret;\n    }\n    ll inv(ll a){\n        return pow(a,P-2);\n    }\n    ll comb(int m,int n){\n        if(m==0||m==n)return 1;\n        else return fac[n]*invfac[m]%P*invfac[n-m]%P;\n    }\n    pair<int,ll> dfs(Tree* t){\n        if(!t)return {0,1};\n        int sl,sr;\n        ll wl,wr;\n        tie(sl,wl)=dfs(t->l);\n        tie(sr,wr)=dfs(t->r);\n        ll w=(wl*wr%P)*comb(sl,sl+sr)%P;\n        return {sl+sr+1,w};\n    }\npublic:\n    int numOfWays(vector<int>& nums) {\n        fac.push_back(1);\n        invfac.push_back(1);\n        for(int i=1;i<=nums.size();i++){\n            fac.push_back(fac.back()*i%P);\n            invfac.push_back(inv(fac.back()));\n        }\n        map<int,Tree*> mp;\n        Tree* root=new Tree(nums[0]);\n        mp[nums[0]]=root;\n        for(int i=1;i<nums.size();i++)\n            insert(mp,nums[i]);\n        return (dfs(root).second+P-1)%P;\n    }\n};\n```
[]