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.
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.