This approach uses divide and conquer combined with combinatorial mathematics to determine the number of ways to reorder an array to produce the same BST. The core idea is to recursively split the array into left and right subarrays (as in constructing the BST) and calculate the number of reorderings for each subtree, using combinations to determine how to arrange elements between left and right subarrays.
Time Complexity: O(n^2), where n is the size of the array, due to the recursive division and combination calculation.
Space Complexity: O(n^2), because of temporary lists created for left and right subarrays.
1import java.util.*;
2
3public class Solution {
4 private static final int MOD = (int)1e9 + 7;
5
6 public int numOfWays(int[] nums) {
7 return (int)(helper(nums) - 1);
8 }
9
10 private long helper(int[] nums) {
11 if (nums.length <= 2) {
12 return 1;
13 }
14 int root = nums[0];
15 List<Integer> left = new ArrayList<>();
16 List<Integer> right = new ArrayList<>();
17 for (int num : nums) {
18 if (num < root) {
19 left.add(num);
20 } else if (num > root) {
21 right.add(num);
22 }
23 }
24 long leftWays = helper(left.stream().mapToInt(i -> i).toArray());
25 long rightWays = helper(right.stream().mapToInt(i -> i).toArray());
26 long comb = comb(left.size() + right.size(), left.size());
27 return (comb * leftWays % MOD) * rightWays % MOD;
28 }
29
30 private long comb(int n, int k) {
31 long res = 1;
32 for (int i = 0; i < k; ++i) {
33 res = res * (n - i) / (i + 1);
34 }
35 return res % MOD;
36 }
37}In this Java solution, we follow a similar logic to the Python implementation. We use helper functions to calculate the number of combinations needed to divide children and recursively find the left and right subtrees, multiplying the number of combs and the recursive calls. Finally, we subtract 1 from the result for the initial sequence inclusion.
Leverage dynamic programming to memoize previously computed results for subarrays. This reduces redundant calculations by storing results of similar subproblems, enabling more efficient computation of the number of reorderings that yield an equivalent BST structure.
Time Complexity: O(n^2), due to dynamic programming table filling and repeated subproblem computations.
Space Complexity: O(n^2), necessary for memoization of the combination results and recursive call stack.
1#include <iostream>
2#include <vector>
3#include <cmath>
4using namespace std;
5
6class Solution {
7 static const int MOD = 1e9 + 7;
8 vector<vector<int>> comb;
9
10 int dfs(vector<int>& nums) {
11 if (nums.size() <= 2) return 1;
12 int root = nums[0];
13 vector<int> left, right;
14 for (int num : nums) {
15 if (num < root) left.push_back(num);
16 if (num > root) right.push_back(num);
17 }
18 long leftWays = dfs(left);
19 long rightWays = dfs(right);
20 return ((combs(left.size() + right.size(), left.size()) * leftWays % MOD) * rightWays) % MOD;
21 }
22
23 int combs(int n, int k) {
24 if (comb[n][k] != -1) return comb[n][k];
25 if (k == 0 || k == n) return 1;
26 return comb[n][k] = (combs(n - 1, k - 1) + combs(n - 1, k)) % MOD;
27 }
28
29public:
30 int numOfWays(vector<int>& nums) {
31 int n = nums.size();
32 comb.resize(n + 1, vector<int>(n + 1, -1));
33 return dfs(nums) - 1;
34 }
35};The C++ code uses a memoization approach to store combination calculations in a comb table. The dfs function divides the array, computes the number of left and right subarray reorderings, and memoizes the combinations calculated. This avoids redundant calculations and optimizes efficiency.