Watch 10 video solutions for Number of Ways to Reorder Array to Get Same BST, a hard level problem involving Array, Math, Divide and Conquer. This walkthrough by Happy Coding has 8,242 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: Given an array of distinct integers, insert the values into a Binary Search Tree in the given order. The task is to count how many different reorderings of the array generate the exact same BST structure. The answer can be large, so results are computed modulo 1e9 + 7.
Approach 1: Divide and Conquer with Combinatorial Counting (O(n^2) time, O(n^2) space)
The first element of the array always becomes the BST root. All smaller values must appear in the left subtree and larger values in the right subtree. Split the remaining elements into two arrays using this rule. Recursively compute the number of valid reorderings for the left and right subtrees. The key insight: while elements must preserve their internal order relative to each subtree, they can interleave in many ways. Use combinations C(leftSize + rightSize, leftSize) to count how many ways the two sequences can merge. Multiply this by the recursive counts from both sides. Precompute combinations using Pascal's triangle or factorials with modular inverse. This technique relies heavily on divide and conquer and combinatorics.
Approach 2: Dynamic Programming with Memoized Combinations (O(n^2) time, O(n^2) space)
This approach uses the same BST partitioning idea but focuses on efficient combination calculation. Instead of recomputing binomial coefficients repeatedly, build a DP table where dp[i][j] stores C(i, j). Fill the table using Pascal's identity: C(n, k) = C(n-1, k-1) + C(n-1, k). During recursion, split the array into left and right partitions based on the root value, recursively compute subtree counts, and combine them with dp[leftSize + rightSize][leftSize]. Memoization prevents recomputation of subtree results. The recursion essentially simulates BST construction while DP handles combinatorial counting. This approach integrates dynamic programming with binary search tree properties.
Recommended for interviews: The divide-and-conquer combinatorial approach is what interviewers expect. It demonstrates understanding of BST insertion rules and combinatorial interleavings. Starting with the recursive partitioning idea shows strong reasoning. Adding precomputed combinations or DP optimization proves you can scale the solution to large inputs efficiently.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer with Combinatorial Counting | O(n^2) | O(n^2) | General case; preferred interview solution using recursion and combinatorics |
| Dynamic Programming with Memoized Combinations | O(n^2) | O(n^2) | When repeatedly computing combinations; avoids recalculating binomial coefficients |