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.

Learn more about Tree, Union Find, Binary Search Tree, Memoization, Math, Divide and Conquer, Dynamic Programming, Binary Tree and Combinatorics patterns.

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.

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.

Solution Implementation

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

Learn more about how to find time and space complexity quickly using problem constraints.