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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 private const int MOD = 1000000007;
6 private int[][] dp;
7
8 public int NumOfWays(int[] nums) {
9 int n = nums.Length;
10 dp = new int[n + 1][];
11 for (int i = 0; i <= n; i++) {
12 dp[i] = new int[n + 1];
13 for (int j = 0; j <= n; j++) {
14 dp[i][j] = -1;
15 }
16 }
17 return (helper(nums) - 1); // -1 to exclude original ordering
18 }
19
20 private int Comb(int n, int k) {
21 if (k == 0 || k == n) return 1;
22 if (dp[n][k] != -1) return dp[n][k];
23 return dp[n][k] = (Comb(n - 1, k - 1) + Comb(n - 1, k)) % MOD;
24 }
25
26 private int helper(int[] nums) {
27 if (nums.Length <= 2) return 1;
28 int root = nums[0];
29 var left = new List<int>();
30 var right = new List<int>();
31 foreach (var num in nums) {
32 if (num < root) left.Add(num);
33 else if (num > root) right.Add(num);
34 }
35 int leftWays = helper(left.ToArray());
36 int rightWays = helper(right.ToArray());
37 return (int)((Comb(left.Count + right.Count, left.Count) * (long)leftWays % MOD) * (long)rightWays % MOD);
38 }
39}This C# solution also employs memoization to store results of computationally expensive combination functions and subproblems. Each recursive call builds left and right partitions, calculating the number of ways to order them recursively while storing the combination results and reusing them via a dynamic programming array.