Easiest Solution!!! | bests 78% of the java coders |
Intuition\nThe intuition behind this code is to use a recursive approach to count the number of ways to split a list of numbers into two non-empty sublists, suc
# Intuition\nThe intuition behind this code is to use a recursive approach to count the number of ways to split a list of numbers into two non-empty sublists, such that the root of the tree is the largest number in the left sublist and the smallest number in the right sublist.\n\nWe can do this by first finding the root of the tree, which is the largest number in the left sublist. Then, we can split the list into two sublists based on whether the numbers are less than or greater than the root. We can then recursively count the number of ways to split each sublist into two non-empty sublists.\n# Approach\nFind the root of the tree, which is the largest number in the left sublist.\n\nSplit the list into two sublists based on whether the numbers are less than or greater than the root.\n\nRecursively count the number of ways to split each sublist into two non-empty sublists.\n\nMultiply the number of ways to split the left sublist by the number of ways to split the right sublist.\n\nReturn the product.\n\n# Complexity\n- Time complexity:\nThe time complexity of this code is O(2^n), where n is the number of nodes in the tree. This is because the recursive algorithm will call itself 2^n times, once for each possible split of the list into two non-empty sublists.\n\n\n- Space complexity:\nThe space complexity of this code is O(n), where n is the number of nodes in the tree. This is because the recursive algorithm will need to store a stack of frames, one for each recursive call.\n\n\n# Code\n```\nclass Solution {\n    private static final int MOD = 1000000007;\n    public int numOfWays(int[] nums) {\n        List<Integer> list = new ArrayList<>();\n        for (int num : nums) {\n            list.add(num);\n        }\n        return countWays(list) - 1;\n    }\n    private int countWays(List<Integer> nums) {\n        if (nums.size() <= 2) {\n            return 1;\n        }\n        \n        List<Integer> left = new ArrayList<>();\n        List<Integer> right = new ArrayList<>();\n        int root = nums.get(0);\n        \n        for (int i = 1; i < nums.size(); i++) {\n            if (nums.get(i) < root) {\n                left.add(nums.get(i));\n            } else {\n                right.add(nums.get(i));\n            }\n        }\n        \n        long leftCount = countWays(left);\n        long rightCount = countWays(right);\n        \n        return (int) ((comb(nums.size() - 1, left.size()) % MOD) * (leftCount % MOD) % MOD * (rightCount % MOD) % MOD);\n    }\n    \n    private long comb(int n, int k) {\n        long[][] dp = new long[n + 1][k + 1];\n        for (int i = 0; i <= n; i++) {\n            dp[i][0] = 1;\n            for (int j = 1; j <= Math.min(i, k); j++) {\n                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;\n            }\n        }\n        return dp[n][k];\n    }\n}\n```
['Java']