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.
1MOD = 10**9 + 7
2
3def numOfWays(nums):
4 from math import comb
5
6 def count(nums):
7 if len(nums) <= 2:
8 return 1
9
10 root = nums[0]
11 left = [x for x in nums if x < root]
12 right = [x for x in nums if x > root]
13 left_count = count(left)
14 right_count = count(right)
15 return comb(len(left) + len(right), len(left)) * left_count * right_count % MOD
16
17 return (count(nums) - 1) % MODThe solution defines a recursive function count(), which calculates the number of ways to split and merge according to the current root node by checking elements less than (left subtree) and greater than (right subtree) the root. The function comb() is used to calculate the number of ways to interleave left and right subtrees, and this is done recursively. The result is reduced by 1 since the original order is not counted as a valid reordering.
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.