Number of Ways to Reorder Array to Get Same BST

    

   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.

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.

 

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.

Example 4:

Input: nums = [3,1,2,5,4,6]
Output: 19

Example 5:

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

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= nums.length
• All integers in nums are distinct.

So, we can know that for a fixed root, the left subtree elements and the right subtree elements are also fixed.

We can find the left subtree elements which are all the elements that is smaller than root value, and right subtree elements which are greater than root value.

And in order to make it identical with original BST, we should keep the relative order in left subtree elements and in right subtree elements.

Assume the length of left subtree elements is left_len and right is right_len, they can change their absolute position but need to keep their relative position in either left subtree or right subtree.

So as the subtree, so we use recursion.

class Solution {

public:

    int numOfWays(vector<int>& nums) 

    {

          long long int mod=1e9+7;

          int n=nums.size();

          table.resize(n+1);

           for(int i=0;i<=n;++i)

           {

               table[i]=vector<long long> (i+1,1);

               for(int j=1;j<i;++j)

               {

                   table[i][j]=(table[i-1][j-1]+table[i-1][j])%mod;

               }

           }

        long long ans=dfs(nums,mod);

       return ans % mod - 1;

    }

private:

vector<vector<long long>> table;

    long long dfs(vector<int> nums,long long int mod)

    {

        int n=nums.size();

          if(n <= 2) return 1;

        vector<int> left,right;

        for(int i=1;i<n;++i)

        {

            if(nums[i]<nums[0])

                left.push_back(nums[i]);

            else 

                right.push_back(nums[i]);

        }

        

        long long int left_res=dfs(left,mod)%mod;

        long long int right_res=dfs(right,mod)%mod;

        

        return ((((table[n-1][left.size()]%mod)*left_res)%mod)*right_res)%mod;

        

    }

};

---------------------------------------------------------------------------------

We separate all the elements into two lists, depending on whether they are less than or more than the root. Then we recurse on those left and right sublists. The combination is for the macro ordering between left and right, and the recursive factors are for the internal ordering of left and right themselves. I minus 1 from the result because we don't count the original ordering.

def numOfWays(self, nums: List[int]) -> int:

    def f(nums):

        if len(nums) <= 2: return 1

        left = [v for v in nums if v < nums[0]]

        right = [v for v in nums if v > nums[0]]

        return comb(len(left)+len(right), len(right)) * f(left) * f(right)

    return (f(nums)-1) % (10**9+7)

----------------------------------------------------------------------------------

This is actually a mathematical problem that can be solved by combination calculation,what'd you do is basically arranging left and right sub-trees in correct order but  in all possible combinations.

For example for array [3,6,4,1]

[3,6,4,1] left subtree is [1], right tree is [6,4], 

we just need to keep 6 appear in front of 4 to make permutation a valid one,

so combinations can be [6,4,1], [6,1,4], [1,6,4]

Obviously, if left subtree length is 1 and the total length is 3, the combination is 3C1 which is 3

Expand to a more complicated case [3,6,4,1,7]

left sub tree is [1], right tree is [6,4,7], 

permutations for right tree itself is [6,4,7], [6,7,4] which means it's 2C1 (combination of [4]

 and [7])

for every permuration of right tree you can also combine it with left tree [1] so total # is 

4C1*2C1=8

Tseudo code:

def dfs(nums):

    if len(nums) <= 2:

        return 1

    left = [x in nums which < nums[0]]

    right = [x in nums which > nums[0]]

    return combination(len(lefft+right), len(left)) * dfs(left) * dfs(right)

Here comes the tricky part for Java, doing mathematical stuff in Java is really a PAIN in the ass

 since it doesn't have comb() function in python and it doesn't support long long, I didn't know 

 why the hint is dynamic programming, now I get it, I can use Yang Hui/Pascal's triangle to speed

  up calculation and get rid of overflow, are you serious leetcode?

class Solution {

    private static final long MOD = 1000000007;

    public int numOfWays(int[] nums) {

        int len = nums.length;

        List<Integer> arr = new ArrayList<>();

        for (int n : nums) {

            arr.add(n);

        }

        return (int)getCombs(arr, getTriangle(len + 1)) - 1;

    }

    

    private long getCombs(List<Integer> nums, long[][] combs) {

        if (nums.size() <= 2) {

            return 1;

        }

        int root = nums.get(0);

        List<Integer> left = new ArrayList<>();

        List<Integer> right = new ArrayList<>();

        for (int n : nums) {

            if (n < root) {

                left.add(n);

            } else if (n > root) {

                right.add(n);

            }

        }

        // mod every number to avoid overflow

        return (combs[left.size() + right.size()][left.size()] * (getCombs(left, combs) % MOD) % MOD) 

        * getCombs(right, combs) % MOD;

    }

    

    private long[][] getTriangle(int n) {

        // Yang Hui (Pascle) triangle

        // 4C2 = triangle[4][2] = 6

        long[][] triangle = new long[n][n];

        for (int i = 0; i < n; i++) {

            triangle[i][0] = triangle[i][i] = 1;

        }

        for (int i = 2; i < n; i++) {

            for (int j = 1; j < i; j++) {

                triangle[i][j] = (triangle[i - 1][j] + triangle[i - 1][j - 1]) % MOD;

            }

        }

        return triangle;

    }

}

---------------------------------------------------------------------------------