[ BST ]✅ || Hard to Easy🔥 || C++⭐, Java🌟 & Python Clear ❄️
Intuition\n- To construct a BST, we need to select a root node and divide the remaining elements into two groups: the left subtree (containing elements smaller 
# Intuition\n- To construct a BST, we need to select a root node and divide the remaining elements into two groups: the left subtree (containing elements smaller than the root) and the right subtree (containing elements larger than the root). The order of elements within each subtree doesn\'t matter as long as the relative order of the elements with respect to the root is maintained.\n\n- Based on this observation, we can approach the problem recursively. For a given array nums, we can select the first element as the root and divide the remaining elements into the left and right subtrees. Then, we recursively count the number of BSTs for the left and right subtrees and multiply them by the number of possible combinations of left and right subtrees. The total count is the product of these values.\n\n---\n# Kindly Vote Sir Please \n![images.jpeg](https://assets.leetcode.com/users/images/41c9663f-37cb-45c2-861f-d6c75bc319b9_1686885458.72043.jpeg)\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. The problem requires counting the number of ways to reorder the given array such that the resulting order yields the same binary search tree (BST). To solve the problem, we can use a recursive approach combined with the concept of Catalan numbers.\n\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n# Time complexity: O(N^3).\nThe time complexity of the solution is determined by the number of recursive calls made to the countBST function. In the worst case, the recursive function will be called for every possible division of the array into left and right subtrees. Since each recursive call reduces the size of the array by one, the number of recursive calls is proportional to the number of elements in the array, which is O(N). Additionally, calculating the binomial coefficients using dynamic programming takes O(N^2) time. Therefore, the overall time complexity is O(N^3).\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n---\n\n\n# Space complexity: O(N^2)\nThe space complexity is determined by the recursion stack used for the recursive calls. In the worst case, the recursion depth can be equal to the number of elements in the array, which is O(N). Additionally, the dynamic programming approach for calculating binomial coefficients requires O(N^2) space for the 2D dp array. Therefore, the overall space complexity is O(N^2).\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n---\n\n# Note \nThe space complexity can be further optimized by using memoization techniques to avoid redundant calculations of binomial coefficients. This can be achieved by storing previously computed values in a memoization table. With memoization, the space complexity can be reduced to O(N) for both time and space.\n\n# Code\n```C++ []\n\nclass Solution {\npublic:\n    int numOfWays(vector<int>& nums) {\n        const int MOD = 1e9 + 7;\n        return (countBST(nums) - 1 + MOD) % MOD;  // Subtract 1 to exclude the original ordering\n    }\n\nprivate:\n    int countBST(vector<int>& nums) {\n        if (nums.size() <= 2)\n            return 1;\n\n        vector<int> left, right;\n        int root = nums[0];\n\n        for (int i = 1; i < nums.size(); i++) {\n            if (nums[i] < root)\n                left.push_back(nums[i]);\n            else\n                right.push_back(nums[i]);\n        }\n\n        long long leftCount = countBST(left);    // Count the number of BSTs for the left subtree\n        long long rightCount = countBST(right);  // Count the number of BSTs for the right subtree\n\n        // Calculate the number of combinations using the Catalan number formula\n        long long totalCount = binomialCoefficient(left.size() + right.size(), left.size());\n\n        return (leftCount * rightCount % 1000000007 * totalCount % 1000000007);\n    }\n\n    long long binomialCoefficient(int n, int k) {\n        const int MOD = 1e9 + 7;\n\n        vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));\n        dp[0][0] = 1;\n\n        for (int i = 1; i <= n; i++) {\n            dp[i][0] = 1;\n            for (int j = 1; j <= min(i, k); j++) {\n                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;\n            }\n        }\n\n        return dp[n][k];\n    }\n};\n\n```\n```Java []\n\nclass Solution {\npublic:\n    int numOfWays(vector<int>& nums) {\n        const int MOD = 1e9 + 7;\n        return (countBST(nums) - 1 + MOD) % MOD;  // Subtract 1 to exclude the original ordering\n    }\n\nprivate:\n    int countBST(vector<int>& nums) {\n        if (nums.size() <= 2)\n            return 1;\n\n        vector<int> left, right;\n        int root = nums[0];\n\n        for (int i = 1; i < nums.size(); i++) {\n            if (nums[i] < root)\n                left.push_back(nums[i]);\n            else\n                right.push_back(nums[i]);\n        }\n\n        long long leftCount = countBST(left);    // Count the number of BSTs for the left subtree\n        long long rightCount = countBST(right);  // Count the number of BSTs for the right subtree\n\n        // Calculate the number of combinations using the Catalan number formula\n        long long totalCount = binomialCoefficient(left.size() + right.size(), left.size());\n\n        return (leftCount * rightCount % 1000000007 * totalCount % 1000000007);\n    }\n\n    long long binomialCoefficient(int n, int k) {\n        const int MOD = 1e9 + 7;\n\n        vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));\n        dp[0][0] = 1;\n\n        for (int i = 1; i <= n; i++) {\n            dp[i][0] = 1;\n            for (int j = 1; j <= min(i, k); j++) {\n                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;\n            }\n        }\n\n        return dp[n][k];\n    }\n};\n\n```\n```Python []\nclass Solution:\n    def numOfWays(self, nums: List[int]) -> int:\n        MOD = 10**9 + 7\n        return (self.countBST(nums) - 1 + MOD) % MOD\n\n    def countBST(self, nums: List[int]) -> int:\n        if len(nums) <= 2:\n            return 1\n\n        left = []\n        right = []\n        root = nums[0]\n\n        for i in range(1, len(nums)):\n            if nums[i] < root:\n                left.append(nums[i])\n            else:\n                right.append(nums[i])\n\n        leftCount = self.countBST(left)\n        rightCount = self.countBST(right)\n\n        totalCount = self.binomialCoefficient(len(left) + len(right), len(left))\n\n        return (leftCount * rightCount * totalCount) % MOD\n\n    def binomialCoefficient(self, n: int, k: int) -> int:\n        MOD = 10**9 + 7\n\n        dp = [[0] * (k + 1) for _ in range(n + 1)]\n        dp[0][0] = 1\n\n        for i in range(1, n + 1):\n            dp[i][0] = 1\n            for j in range(1, min(i, k) + 1):\n                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD\n\n        return dp[n][k]\n\n```\n
['Divide and Conquer', 'Dynamic Programming', 'C++']