1569. Number of Ways to Reorder Array to Get Same BST


Problem Description

In this problem, we're given a list of numbers, nums, which is a permutation of the integers from 1 to n. Our task is to construct a binary search tree (BST) using the elements of nums, by inserting them one by one into an initially empty BST, in the same order as they appear in nums. After constructing the BST, we want to determine the total number of different ways we can reorder the elements of nums so that, if we were to construct a BST with each reordered list, the structure of the resulting BST would be exactly the same as the BST constructed from the original nums list.

It’s important to note that a BST is a binary tree where each node has up to two children, and for every node, all the elements in its left subtree are less than the node's value, and all the elements in its right subtree are greater than the node's value.

Let's consider an example. Suppose nums = [2,1,3]. The resulting BST would have 2 as the root, 1 as the left child, and 3 as the right child. If we reorder nums to [2,3,1], we would still construct the identical BST with these elements: 2 as the root, 1 as the left child, and 3 as the right child. However, a different order like [3,2,1] would yield a different BST structure.

Because the number of reorderings could be extremely large, we are asked to return the result modulo 10^9 + 7.

Intuition

To solve this problem, we take a divide-and-conquer approach, utilizing recursion.

  1. Dividing the problem: The BST's structure is decided by which node is the root. In a sorted permutation, the first number will always be the root. Hence, the numbers that come after it can be separated into those that would go into the left subtree (smaller than the root) and those that would go into the right subtree (larger than the root).

  2. Conquering the subproblems: After dividing the nums array into left and right subtrees based on the root, we recursively repeat the same process for each subtree. The recursion base case happens when we reach a subtree with less than two elements, at which point there's only one way to insert them into the BST.

  3. Combining the results: Each subtree can be reordered in some number of ways without changing the structure of the BST. To know how many ways we can merge the nodes of two subtrees without affecting the BST's structure, we use the combination formula C(m+n, m) = (m+n)! / (m! * n!), where m is the size of the left subtree and n is the size of the right subtree. This formula gives us the count of ways we can pick positions for the left subtree among all positions of combined subtrees.

  4. Take care of the modulo: The result can get very large, and to prevent integer overflow and meet the problem's requirements, we perform modulo operation at every multiplication or addition.

  5. Subtracting one: After calculating all possible reorderings including the original order, we subtract one from the result, as the problem asks for the count of different ways to reorder nums excluding the original order.

  6. Preprocessing combinations: To avoid calculating factorial and combination values repeatedly, we can pre-calculate all the binomial coefficients (combination counts) needed for the problem and store them for future reference.

By breaking down our nums array into smaller arrays representing the left and right subtrees, recursively solving for those subtrees, and then combining those results with the help of the combination formula, we can find the total count of reorderings that keep the BST structure unchanged.

Solution Approach

The solution provided in the reference approach involves a recursive function that tackles each subproblem of constructing a BST from a given array and uses dynamic programming for calculating combinations efficiently. Here’s how it breaks down:

  1. Recursion (Divide and Conquer): We construct a recursive function dfs(nums) that handles the construction of a BST given a list of numbers. The process involves identifying the root (the first element in the current list), partitioning the remaining elements into left and right subtrees (elements less than the root to the left and greater than the root to the right), and then recursively calling dfs() on these subtrees.

  2. Computation of Combinations (Dynamic Programming): Since we need to calculate combinations to find out how many ways we can merge the nodes of the left and right subtrees, we pre-compute a combination table c using dynamic programming. This table will hold the values of C(m+n, m), which gives us the number of ways to choose m positions from m + n options. The values are calculated using the relationship c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod, where mod is 10^9 + 7.

  3. Combining the Counts: After obtaining the number of reorderings for the left subtree a and the right subtree b through recursive calls, we combine them using the precomputed combination values from the table. Thus, the total number of reorderings is calculated by multiplying the number of ways to choose positions for the left subtree (c[m + n][m]) with the recursive solutions of left a and right b subtrees: (((c[m + n][m] * a) % mod) * b) % mod.

  4. Modulo Operation: To ensure that the calculated values do not exceed the range of integer values allowed and to comply with the problem’s requirements to return the result modulo 10^9 + 7, we take the modulo after each multiplication and addition operation.

  5. Result Adjustment: The result from dfs(nums) includes the original ordering, which shouldn't be counted according to the problem statement. Therefore, we subtract 1 from the solution obtained from the recursive function and then take modulo mod to get the final result.

In summary, the implementation of the solution uses a combination of recursion for constructing the BST in a divide-and-conquer manner, dynamic programming for efficient calculation of combinations, and careful application of the modulo operation to stay within prescribed limits.

Here is the code snippet highlighted in the solution:

1def dfs(nums):
2    if len(nums) < 2:
3        return 1
4    left = [x for x in nums if x < nums[0]]
5    right = [x for x in nums if x > nums[0]]
6    m, n = len(left), len(right)
7    a, b = dfs(left), dfs(right)
8    return (((c[m + n][m] * a) % mod) * b) % mod
1c = [[0] * n for _ in range(n)]
2c[0][0] = 1
3for i in range(1, n):
4    c[i][0] = 1
5    for j in range(1, i + 1):
6        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod

Together, these two blocks of code demonstrate the core logic of the solution, where recursion and dynamic programming converge to solve the problem.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's use a simple example to illustrate the solution approach. Suppose nums = [3, 2, 1, 4]. This sequence is a permutation of numbers from 1 to 4, and we want to insert these numbers one by one into a BST.

The original BST constructed from nums would look like this:

1    3
2   / \
3  2   4
4 /
51

Now, we want to determine how many ways we can reorder nums so that the structure of the BST remains the same.

The solution approach is as follows:

  1. Kick off the recursion: Call the dfs function with the original nums. The first element 3 becomes our root.

  2. Partition into subtrees: We split nums into a left subtree of all elements less than 3 ([2, 1]), and a right subtree of all elements greater than 3 ([4]).

  3. Recurse on subtrees: We recursively call dfs on [2, 1] and [4]. For the single element tree [4], the dfs will return 1 immediately.

  4. Calculate for the left subtree [2, 1]:

    4.1. We identify 2 as the root for this subtree.

    4.2. The remaining element 1 forms the left subtree of 2.

    4.3. Since there is only one way to insert 1 into the subtree with root 2, dfs on [1] returns 1.

  5. Combining subtrees: We now need to combine the possibilities of the left and right subtrees into the main tree with root 3.

    • Since the left subtree has length 2 and the right subtree has length 1, we calculate the combinations C(2+1, 2) to determine the number of ways to merge these trees while keeping the BST structure.
  6. Utilize the precomputed combinations: Access the precomputed combination table c to get C(2+1, 2). Let's assume c[3][2] is already computed and is equal to 3 for this example.

  7. Calculate the total count for the current partition: Multiply the counts from the left and right subtrees and combine it with the combination count. In this case, it is (3 (c[3][2]) * 1 (left subtree) * 1 (right subtree)) % mod. Since there is only one way for each subtree, our total here is simply 3.

  8. Adjustment for original ordering: Since our result is supposed to exclude the original ordering, we subtract 1 from the total. For our example 3 - 1 = 2 ways to reorder nums to have the same BST structure, excluding the original order.

Therefore, the number of ways to reorder [3, 2, 1, 4] such that the structure of the BST remains the same (excluding the original order) is 2. The possible reorderings are [3, 1, 2, 4] and [3, 4, 2, 1]. In both cases, the structure of the BST formed is identical to the BST structure formed from the original nums.

Python Solution

1from typing import List
2
3class Solution:
4    def number_of_ways(self, nums: List[int]) -> int:
5        # Define a recursive function to calculate the number of BSTs for the given list.
6        def count_bsts(sub_nums):
7            # Base case: if the list is empty or has only one element, there is only one way to construct a BST.
8            if len(sub_nums) < 2:
9                return 1
10          
11            # Split the nums based on the current root, which is the first element in the list.
12            left_subtree = [x for x in sub_nums if x < sub_nums[0]]
13            right_subtree = [x for x in sub_nums if x > sub_nums[0]]
14          
15            # Calculate the possibilities of left and right subtrees.
16            left_ways = count_bsts(left_subtree)
17            right_ways = count_bsts(right_subtree)
18          
19            # Calculate the combination count using precomputed combination values.
20            left_size = len(left_subtree)
21            right_size = len(right_subtree)
22          
23            # Calculate the result as the product of left ways, right ways, and the combination count.
24            # Mod operations are used to keep the values within integer limits specified by the problem.
25            return ((comb[left_size + right_size][left_size] * left_ways) % MOD) * right_ways % MOD
26
27        # Length of the input list of numbers.
28        n = len(nums)
29        # The modulo value given by the problem to perform operations under this modular arithmetic.
30        MOD = 10 ** 9 + 7
31      
32        # Initialize combination values for future use in the recursive function to calculate combos (binomial coefficients).
33        comb = [[0] * n for _ in range(n)]
34        # The first column of Pascal's Triangle (nC0) is 1.
35        for i in range(n):
36            comb[i][0] = 1
37      
38        # Populate Pascal's Triangle to find combinations (nCr) under modulo MOD.
39        for i in range(1, n):
40            for j in range(1, i + 1):
41                comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD
42      
43        # The final count needs to subtract 1 to not count the initial empty BST.
44        # Then, we also ensure the result is in the correct modulo range by adding MOD and again applying mod.
45        return (count_bsts(nums) - 1 + MOD) % MOD
46
47# Example usage:
48# sol = Solution()
49# print(sol.number_of_ways([3,1,2,5,4,6]))
50

Java Solution

1class Solution {
2    private int[][] combinationMatrix;
3    private static final int MOD = (int) 1e9 + 7;
4
5    public int numOfWays(int[] nums) {
6        int n = nums.length;
7        combinationMatrix = new int[n][n];
8        // Base case for nCr (n Choose r)
9        combinationMatrix[0][0] = 1;
10        // Populate the combination matrix
11        for (int i = 1; i < n; ++i) {
12            combinationMatrix[i][0] = 1;
13            for (int j = 1; j <= i; ++j) {
14                combinationMatrix[i][j] = (combinationMatrix[i - 1][j] + combinationMatrix[i - 1][j - 1]) % MOD;
15            }
16        }
17        // Convert the array to List for easier manipulation
18        List<Integer> list = new ArrayList<>();
19        for (int number : nums) {
20            list.add(number);
21        }
22        // Calculate the number of ways and adjust for the one subtracted way
23        return (dfs(list) - 1 + MOD) % MOD;
24    }
25
26    // Helper method to recursively calculate the number of possible unique BSTs
27    private int dfs(List<Integer> nums) {
28        // If we are down to one or no elements, there's only one way to arrange
29        if (nums.size() < 2) {
30            return 1;
31        }
32        List<Integer> leftSubtree = new ArrayList<>();
33        List<Integer> rightSubtree = new ArrayList<>();
34        // Divide the remaining numbers into left and right subtrees
35        for (int number : nums) {
36            if (number < nums.get(0)) {
37                leftSubtree.add(number);
38            } else if (number > nums.get(0)) {
39                rightSubtree.add(number);
40            }
41        }
42        // Calculate the number of ways for left and right subtrees
43        int leftCount = dfs(leftSubtree), rightCount = dfs(rightSubtree);
44        int totalSubtrees = leftSubtree.size() + rightSubtree.size();
45      
46        // Calculate the total combinations using the combination matrix
47        return (int) (((long) leftCount * rightCount % MOD) * combinationMatrix[totalSubtrees][rightSubtree.size()] % MOD);
48    }
49}
50

C++ Solution

1#include <vector>
2#include <functional>
3#include <cstring>
4using namespace std;
5
6class Solution {
7public:
8    int numOfWays(vector<int>& nums) {
9        size_t n = nums.size();
10        const int MOD = static_cast<int>(1e9) + 7;
11      
12        int combinations[n][n];
13        memset(combinations, 0, sizeof(combinations)); // Initialize to zero
14      
15        combinations[0][0] = 1;
16        // Compute combinatorics for numbers [0, n-1]
17        for (size_t i = 1; i < n; ++i) {
18            combinations[i][0] = 1;
19            for (size_t j = 1; j <= i; ++j) {
20                combinations[i][j] = (combinations[i - 1][j] + combinations[i - 1][j - 1]) % MOD;
21            }
22        }
23      
24        // Define recursive lambda function for computing the number of BSTs
25        function<int(vector<int>)> countBSTs = [&](vector<int> currentNums) -> int {
26            if (currentNums.size() <= 1) {
27                return 1; // A single node or empty tree has only one configuration
28            }
29            vector<int> leftSubtree, rightSubtree;
30          
31            // Partition the numbers into left and right subtrees based on the value of the root (currentNums[0])
32            for (int x : currentNums) {
33                if (x < currentNums[0]) {
34                    leftSubtree.push_back(x);
35                } else if (x > currentNums[0]) {
36                    rightSubtree.push_back(x);
37                }
38            }
39          
40            size_t leftSize = leftSubtree.size(), rightSize = rightSubtree.size();
41            int leftCount = countBSTs(leftSubtree), rightCount = countBSTs(rightSubtree);
42          
43            // Calculate the number of BSTs for current partition
44            return static_cast<long long>(combinations[leftSize + rightSize][leftSize]) * leftCount % MOD * rightCount % MOD;
45        };
46      
47        // Subtracting one because the problem might expect the number of ways excluding the initial sequence
48        return (countBSTs(nums) - 1 + MOD) % MOD;
49    }
50};
51

Typescript Solution

1// Helper function to compute binomial coefficients modulo a given value (mod)
2function calculateBinomialCoefficients(n: number, mod: number): number[][] {
3    const coefficients = new Array(n).fill(0).map(() => new Array(n).fill(0));
4    coefficients[0][0] = 1;
5
6    for (let i = 1; i < n; ++i) {
7        coefficients[i][0] = 1;
8        for (let j = 1; j <= i; ++j) {
9            coefficients[i][j] = (coefficients[i - 1][j - 1] + coefficients[i - 1][j]) % mod;
10        }
11    }
12
13    return coefficients;
14}
15
16// Recursive function to calculate the number of ways to reorder nums such that the resultant binary search tree's
17// in-order traversal is nums sorted in ascending order
18function countWays(nums: number[], coefficients: number[][], mod: number): number {
19    // Base case: if nums has less than 2 elements, there is only one way
20    if (nums.length < 2) {
21        return 1;
22    }
23
24    const leftSubtree = [];
25    const rightSubtree = [];
26  
27    // Construct left and right subtrees arrays
28    for (let i = 1; i < nums.length; ++i) {
29        if (nums[i] < nums[0]) {
30            leftSubtree.push(nums[i]);
31        } else {
32            rightSubtree.push(nums[i]);
33        }
34    }
35
36    // Recursively solve for left and right subtrees
37    const leftWays = countWays(leftSubtree, coefficients, mod);
38    const rightWays = countWays(rightSubtree, coefficients, mod);
39
40    // Calculate and combine the ways from left and right subtrees using binomial coefficient
41    const total = (BigInt(coefficients[leftSubtree.length + rightSubtree.length][leftSubtree.length])
42                  * BigInt(leftWays)
43                  * BigInt(rightWays)) % BigInt(mod);
44                
45    return Number(total);
46}
47
48// Main function to calculate number of ways to reorder nums
49function numOfWays(nums: number[]): number {
50    const n = nums.length;
51    const mod = 1e9 + 7;
52
53    // Precompute binomial coefficients used in the calculation
54    const coefficients = calculateBinomialCoefficients(n, mod);
55
56    // Compute the number of ways and subtract 1 for the initial sequence
57    const ways = countWays(nums, coefficients, mod) - 1;
58
59    // Ensure the result is positive and return it modulo mod
60    return (ways + mod) % mod;
61}
62
63// Sample usage of the function
64const nums = [3,1,2,5,4,6];
65console.log(numOfWays(nums)); // Output the number of ways to reorder
66

Time and Space Complexity

The time complexity of the provided code is indeed O(n^2). This arises from the following considerations:

  1. The construction of the combination table c requires O(n^2) time because we have a nested loop that fills the table with binomial coefficients. The outer loop runs n times and the inner loop runs up to i times, leading up to a triangular number series, the sum of which is (n * (n - 1)) / 2, which simplifies to O(n^2).

  2. The dfs function is called recursively, at most, for each element of nums. Within each call to dfs, we split the list into left and right, which requires O(n) time each due to the list comprehension going through the remaining elements. The total number of operations done across all the recursive calls also results in O(n^2) time complexity. This is because the number of operations is bounded by the number of ways to construct binary search trees (BSTs), known as the Catalan number, which has an upper bound of 4^n / (n^(3/2)) that simplifies to O(n^2) when multiplied by O(n) complexity of the list comprehension.

In terms of space complexity, the code also has O(n^2) space complexity due to the following:

  1. The combination table c takes up O(n^2) space since it is essentially an n x n matrix.

  2. The recursion stack depth can go up to O(n) in the worst case (e.g., the input is a sorted array), and within each call, we are creating new lists left and right. However, since these lists collectively hold a subset of the original input, and the storage used by all calls collectively does not exceed O(n), the additional space complexity is linear with respect to the input. Therefore, the dominant term for space complexity is the space taken by the combination table, which remains O(n^2).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫