10:I[13699,["/_next/static/chunks/6b91a202b724e571.js","/_next/static/chunks/6710f67d945945a1.js","/_next/static/chunks/bde5ef9330c4de2d.js"],"default"] 11:I[25152,["/_next/static/chunks/6b91a202b724e571.js","/_next/static/chunks/6710f67d945945a1.js","/_next/static/chunks/bde5ef9330c4de2d.js"],"default"] 12:T463,class Solution { long[][] comb; long MOD = 1000000007; public int numOfWays(int[] nums) { int n = nums.length; comb = new long[n][n]; for (int i = 0; i < n; i++) { comb[i][0] = comb[i][i] = 1; for (int j = 1; j < i; j++) { comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD; } } List list = new ArrayList<>(); for (int num : nums) list.add(num); return (int)((dfs(list) - 1 + MOD) % MOD); } private long dfs(List list) { if (list.size() < 3) return 1; List left = new ArrayList<>(); List right = new ArrayList<>(); int root = list.get(0); for (int i = 1; i < list.size(); i++) { if (list.get(i) < root) left.add(list.get(i)); else right.add(list.get(i)); } long leftWays = dfs(left); long rightWays = dfs(right); int m = list.size(); long ways = (leftWays * rightWays) % MOD; return (ways * comb[m - 1][left.size()]) % MOD; } }13:T410,class Solution { long long MOD = 1e9 + 7; vector> comb; public: int numOfWays(vector& nums) { int n = nums.size(); comb.resize(n, vector(n)); for (int i = 0; i < n; ++i) { comb[i][0] = comb[i][i] = 1; for (int j = 1; j < i; ++j) { comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD; } } return (dfs(nums) - 1 + MOD) % MOD; } long long dfs(vector& nums) { int m = nums.size(); if (m < 3) return 1; vector left_nodes, right_nodes; for (int i = 1; i < m; ++i) { if (nums[i] < nums[0]) left_nodes.push_back(nums[i]); else right_nodes.push_back(nums[i]); } long long left_ways = dfs(left_nodes); long long right_ways = dfs(right_nodes); long long total = (left_ways * right_ways) % MOD; return (total * comb[m - 1][left_nodes.size()]) % MOD; } };

Time Complexity

Space Complexity