[Java][Python] 2 Approch|| Faster than 96.8% Using Pascal's Tringle in java and combinatories , BST
Intuition\n Describe your first thoughts on how to solve this problem. \n- Intuition for Java:(using Pascal\'s Tringle)\nwe uses a recursive approach combined w
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- **Intuition for Java:(using Pascal\'s Tringle)**\nwe uses a recursive approach combined with the Pascal\'s Triangle to calculate the number of ways to arrange the elements in the input array. It separates the elements into two sublists based on their values and recursively calculates the number of ways for each sublist. The final result is obtained by multiplying the number of ways for the sublists and the corresponding combination from the Pascal\'s Triangle.\n\n- **Intuition for Python:(by recursively)**\nWe uses a recursive approach to calculate the number of ways to arrange the elements in the input array. It separates the elements into two sublists based on their values and then recursively calculates the number of ways for each sublist. The final result is obtained by multiplying the number of ways for the sublists and the appropriate combination value.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- **Approach for Java-using Pascal\'s Tringle:**\n\nThe code defines a Solution class that contains the necessary methods and variables.\n\nThe code initializes a constant MOD with the value 1000000007. This constant is used to perform modulo arithmetic.\n\nThe code initializes a constant 2D array pascal_triangle using the BuildPascalsTriangle function. This array stores the Pascal\'s Triangle up to a size of 1000. Each element of the array represents the combination of choosing j elements from a set of i elements.\n\nThe numOfWays method takes an input array nums and converts it to a list. It then calls the NumsOfWays method to calculate the number of ways to arrange the array.\n\nThe NumsOfWays method recursively calculates the number of ways to arrange the elements in the input list nums. It first checks if the size of nums is less than or equal to 2. If so, it returns 1 since there is only one way to arrange 0 or 1 elements.\n\nIf nums has more than 2 elements, the method separates the elements into two lists: leftNodes and rightNodes. The leftNodes list contains elements smaller than the first element (root), and the rightNodes list contains elements greater than the first element.\n\nThe method recursively calls NumsOfWays on leftNodes and rightNodes to calculate the number of ways to arrange the elements in each sublist.\n\nThe method uses the formula: (NumsOfWays(leftNodes) * NumsOfWays(rightNodes) * pascal_triangle[n-1][leftNodes.size()]) % MOD to calculate the total number of ways to arrange the elements in nums. It multiplies the number of ways to arrange the left sublist by the number of ways to arrange the right sublist, and multiplies the result by the corresponding combination from the Pascal\'s Triangle.\n\nFinally, the method returns the calculated number of ways modulo MOD.\n\nThe BuildPascalsTriangle method constructs the Pascal\'s Triangle as a 2D array. It initializes the edges of the triangle with 1, and then fills in the remaining elements using the formula: pascal_triangle[i][j] = (pascal_triangle[i-1][j] + pascal_triangle[i-1][j-1]) % MOD.\n\n- **Approch for Python:**\n\nThe code defines a Solution class that contains the necessary methods and variables.\n\nThe code initializes a variable mod with the value 10 ** 9 + 7. This variable is used to perform modulo arithmetic.\n\nThe code defines a helper function combination(nl, nr) that calculates the combination of choosing nr elements from a set of nl + nr elements. It uses a precalculated array factorial to efficiently compute the combination.\n\nThe code defines a recursive helper function ways(arr) that calculates the number of ways to arrange the elements in the input list arr.\n\nIf the length of arr is less than or equal to 2, there is only one way to arrange the elements, so the function returns 1.\n\nOtherwise, the function selects the first element of arr as the root. It then separates the remaining elements into two sublists: left (containing elements smaller than the root) and right (containing elements greater than the root).\n\nThe function recursively calls itself on left and right to calculate the number of ways to arrange the elements in each sublist.\n\nThe function multiplies the number of ways for left and right by the combination of choosing the appropriate number of elements from each sublist. This is done using the combination function.\n\nFinally, the function returns the product of the calculated number of ways for left and right, modulo mod.\n\nThe main function numOfWays initializes a variable n with the length of the input array nums.\n\nIt also initializes an array factorial with length n and fills it with factorial values from 1 to n. This array is used to efficiently calculate combinations in the combination function.\n\nThe function calls ways(nums) to calculate the number of ways to arrange the elements in nums and subtracts 1 from it.\n\nFinally, the function returns the result modulo mod.\n\n# Complexity\n- Time complexity:O(2^n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- **for java code**\n\nThe numOfWays method initially converts the nums array to a List<Integer>. This conversion takes O(n) time, where n is the size of the nums array.\n\nThe NumsOfWays method recursively splits the input list into two sublists, leftNodes and rightNodes. The size of each sublist can be at most n-1, where n is the size of the original list. The recursion continues until the sublist size becomes 2 or less. Therefore, the time complexity of the NumsOfWays method is O(2^n).\n\nThe BuildPascalsTriangle method constructs a 2D array of size n x n, where n is set to 1000. The nested loops iterate n times each, resulting in a time complexity of O(n^2), which can be considered constant as 1000 is a fixed value.\n\nOverall, the time complexity of the code is dominated by the NumsOfWays method, which is O(2^n).\n\n- **for python code**\nThe combination function calculates the factorial of the sum of two inputs and performs two divisions. This takes constant time, so its time complexity is O(1).\n\nThe ways function recursively calls itself for left and right sublists. The size of each sublist can be at most n-1, where n is the size of the original list. Therefore, the recurrence relation for the time complexity of the ways function can be expressed as T(n) = 2T(n-1) + O(1), where T(n) is the time complexity for an input of size n. By expanding the recursion, we can see that T(n) is exponential, specifically O(2^n).\n\nThe loop in the numOfWays method iterates n times to calculate the factorial array. Each iteration performs multiplication, so the time complexity of this loop is O(n).\n\nOverall, the time complexity of the code is dominated by the ways function, which is O(2^n).\n\n- Space complexity:O(2^n) for java / O(n^2) for python\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- **for java code**\nThe numOfWays method takes an input array nums of size n. It creates two additional lists, leftNodes and rightNodes, which can potentially store all n elements of nums. Therefore, the space complexity of the numOfWays method is O(n).\n\nThe BuildPascalsTriangle method creates a 2D array pascal_tringle of size n x n, where n is set to 1000. Hence, the space complexity of this method is O(n^2), which can be considered constant as 1000 is a fixed value.\n\nOverall, the space complexity of the code is O(n + n^2), which simplifies to O(n^2) as the dominant term.\n\n- **for python code**\nThe combination function takes constant space, so its space complexity is O(1).\n\nThe ways function recursively creates new lists for the left and right sublists. The maximum depth of recursion can be n, and at each recursion level, two new lists are created. Therefore, the space complexity of the ways function is O(2^n).\n\nThe numOfWays method creates the factorial array of size n. Hence, the space complexity for this array is O(n).\n\nOverall, the space complexity of the code is O(2^n) due to the ways function and O(n) for the factorial array, resulting in a total space complexity of O(2^n + n).\n\n\n# Code\n```Java []\nclass Solution {\n\n    private static final long MOD = 1000000007;\n    private static final long[][] pascal_tringle = BuildPascalsTriangle();\n\n    public int numOfWays(int[] nums) {\n        List<Integer> arr = Arrays.stream(nums).boxed().collect(Collectors.toList()) ;\n        \n        return (int)((NumsOfWays(arr)-1) % MOD);\n    }\n\n    private long NumsOfWays(List<Integer> nums) {\n        int n = nums.size();\n        if (n <= 2) return 1;\n\n        List<Integer> leftNodes = new ArrayList<>();\n        List<Integer> rightNodes = new ArrayList<>();\n\n        int root = nums.get(0);\n        for (int i=1; i<n; i++) {\n            if (nums.get(i) < root) {\n                leftNodes.add(nums.get(i));\n            } else {\n                rightNodes.add(nums.get(i));\n            }\n        }\n\n        return (((NumsOfWays(leftNodes) % MOD * NumsOfWays(rightNodes) % MOD) % MOD) * \n        pascal_tringle[n-1][leftNodes.size()]) % MOD;\n    }\n\n    private static long[][] BuildPascalsTriangle() {\n        int n=1000;\n        long[][] pascal_tringle = new long[n][n];\n\n        for (int i=0; i<n; i++) {\n            pascal_tringle[i][0] = pascal_tringle[i][i] = 1;\n        }\n        for (int i=2; i<n; i++) {\n            for (int j=1; j<i; j++) {\n                pascal_tringle[i][j] =\n                 (pascal_tringle[i-1][j] + pascal_tringle[i-1][j-1]) % MOD;\n            }\n        }\n        return pascal_tringle;\n    }\n}\n```\n```Python []\nclass Solution:\n    def numOfWays(self, nums: List[int]) -> int:\n\n        mod = 10 ** 9 + 7\n\n        def combination(nl,nr):\n            return factorial[nl+nr] // factorial[nl] // factorial[nr]\n\n\n        def ways(arr):\n           if len(arr)<=2:\n               return 1\n\n           root = arr[0]\n\n           left = [num for num in arr if num < root ]\n           right = [ num for num in arr if num > root]\n          \n           return ways(left) * ways(right) * combination(len(left), len(right))\n\n        n = len(nums)\n        factorial = [1] * (n)\n\n        for i in range(1,n):\n            factorial[i]= factorial[i-1] * i\n\n        return (ways(nums)-1) % mod;  \n\n```\n\n
['Java', 'Python3']