This page explains Java solution to problem `Number of Ways to Reorder Array to Get Same BST`

using `Dynamic Programming`

algorithm.

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`

.

For example, given `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 `10^`

.
^{9} + 7

Input: nums = [2,1,3]Output: 1Explanation: 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.

Input: [3,4,5,1,2]Output: 5Explanation: 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]

Input: nums = [1,2,3]Output: 0

Input: nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]Output: 216212978Explanation: The number of ways to reorder nums to get the same BST is 3216212999. Taking this number modulo 10^^{9}+ 7 gives 216212978.

```
package com.vc.hard;
import java.util.*;
class NumberOfWaysToReorderArrayToGetSameBst {
private long[][] pascal;
private int MOD = (int)1e9 + 7;
public int numOfWays(int[] nums) {
int n = nums.length;
generatePascal(n + 1);
List<Integer> numbers = new ArrayList<>();
for(int i = 0; i < nums.length; i++) numbers.add(nums[i]);
//-1 because one permutation is already given as an input
return (int)helper(numbers) - 1;
}
private long helper(List<Integer> nums) {
if(nums.size() <= 2) return 1;
int root = nums.get(0);
List<Integer> left = new ArrayList<>();
List<Integer> right = new ArrayList<>();
for(int i = 1; i < nums.size(); i++) {
int num = nums.get(i);
if(num > root) right.add(num);
else left.add(num);
}
/**
How many different ways we can arrange left.size() elements in left.size() + right.size() elements
Let's say we have [3, 4, 5, 1, 2] as original array with root value is 3
[1, 2] left sub-tree, left.size() = 2
[4, 5] right sub-tree, right.size() = 2
In all of below permutations, we keep relative position in left & right subtree,
But we can absolute position
[1, 2, 4, 5]
[1, 4, 2, 5]
[1, 4, 5, 2]
[4, 1, 2, 5]
[4, 1, 5, 2]
[4, 5, 1, 2]
*/
return pascal[left.size() + right.size()][left.size()] % MOD *
helper(left) % MOD *
helper(right) % MOD;
}
private void generatePascal(int n) {
pascal = new long[n][n];
for(int row = 0; row < n; row++) pascal[row][0] = pascal[row][row] = 1;
for(int row = 2; row < n; row++) {
for(int col = 1; col < row; col++) {
pascal[row][col] = (pascal[row - 1][col] + pascal[row - 1][col - 1]) % MOD;
}
}
}
}
```

O(N

^{2}) Where

N is number of elements in an input array nums

O(N * N) Where

N is number of elements in an input array nums