StaffArrayBinary Search TreeBinary TreeCombinatoricsDivide and ConquerDynamic ProgrammingMathMemoizationTreeUnion-Find
Number of Ways to Reorder Array to Get Same BST
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.
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 10^9 + 7.
Example 1
Input
nums = [2,1,3]Output
1We can reorder nums to be [2,3,1], which will yield the same BST, and there are no other valid reorderings.
Example 2
Input
nums = [3,4,5,1,2]Output
5The 5 arrays [3,1,2,4,5], [3,1,4,2,5], [3,1,4,5,2], [3,4,1,2,5], and [3,4,1,5,2] will yield the same BST.
Constraints
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= nums.length
- All integers in nums are distinct.
Asked at 2 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.