Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.
nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [2,1,3] Output: 1 Explanation: We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.
Example 2:
Input: nums = [3,4,5,1,2] Output: 5 Explanation: The following 5 arrays will yield the same BST: [3,1,2,4,5] [3,1,4,2,5] [3,1,4,5,2] [3,4,1,2,5] [3,4,1,5,2]
Example 3:
Input: nums = [1,2,3] Output: 0 Explanation: There are no other orderings of nums that will yield the same BST.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= nums.lengthnums are distinct.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.
The 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.
Java
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.
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.
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.
C#
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.
| Approach | Complexity |
|---|---|
| Divide and Conquer with Combinatorial Counting | Time Complexity: O(n^2), where n is the size of the array, due to the recursive division and combination calculation. |
| Dynamic Programming | Time Complexity: O(n^2), due to dynamic programming table filling and repeated subproblem computations. |
LeetCode 1569. Number of Ways to Reorder Array to Get Same BST • Happy Coding • 8,162 views views
Watch 9 more video solutions →Practice Number of Ways to Reorder Array to Get Same BST with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor