Leetcode 1569. Number of Ways to Reorder Array to Get Same BST

 https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/description/

Notes:

If I say if you know how to solve the walking robot question, then you should know how to solve this question, you will not believe it. Will you? 

If you do know how to solve the robot question, but still cannot solve this one, no worry, let start this question step by step.

This question can be transformed to a similar question with a smaller size. Thus it can be solved recursively or using dp for optimization.

Let us look at an example: [3, 4, 5, 1, 2]

in the first step: the left sub tree = [1, 2], and the right sub tree = [4, 5]

then in order to solve the original question, we need to solve the same question for these two sub trees.

Now let us work on the relation from the sub tree to the root tree. If we know there are x ways for the left sub tree, and y ways for the right sub tree. Then the question becomes how many ways for the root tree?

The first response is that: if left sub tree and right sub tree cannot be mixed, then there will be x*y ways for root tree. However, the left sub tree can mix with the right sub tree. And this is why this question is labeled as hard.

Let us continue to use the above example: there are 2 elements in the left sub tree and 2 as well in the right. As an initial try, we can place 1 from the left to three different positions: before 4, before 5, after 5, which are listed below:

1): [1, 4, 5]

2): [4, 1, 5]

3): [4, 5, 1]

Then we need to place 2 from left to each of the above three cases: the rule is that 2 has to be placed after 1

Thus, 

for 1): there are 3 places for 2; 

for 2): there are 2 places for 2;

for 3): there are 1 place for 2.

In total, there are 3 + 2 + 1 = 6 ways. Based on the question example, we need to remove the original one, thus the answer is 5.

So one of an important observations for mixing is that: for a fixed left and right array (or serialized tree sequence), the relative order of the left and right needs to be maintained. Then this question becomes a pure combination/permutation problem!

Let say we have m elements in the left, n elements in the right, and we are going to mix them, and we need to keep the relative orders of the elements in the left and right for the mixing. Then the answer is: (m+n)!/(m!*n!). So basically it is the full permutation of all these elements, divided by the full permutation of m and full permutation of n (since we have to keep the relative orders in the left and right.)

So you can use mathematical formula directly to calculate this one, but for fun, let us look at a different way to solve it using programming.

If you by any chance be aware of another question: walking robot (from most left up corner to the most right down corner, and can only walk down or right one step a time), then the ways of mixing is the same as the ways of the robot can go from the most left up corner to the most right down corner!!!

So we can use dp to solve the ways of mixing: dp[i][j] = dp[i][j-1] + dp[i-1][j]

With mixing solved, we need to look at back to the original question: there are x*y ways for the left and right without mixing; if the mixing is allowed, then there are x*y*dp[i][j], where i and j are the element numbers in the left sub tree and the right sub tree, respectively.

If you still have question, please leave it below. Any comment/discussion is welcome!

See the code below:

class Solution {
public:
    int numOfWays(vector<int>& nums) {
        int n = nums.size();
        vector<vector<long>> dp(n, vector<long>(n, 1));
        for(int i=1; i<n; ++i) {
            for(int j=1; j<n; ++j) {
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
                dp[i][j] %= mod;
            }
        }
        return (dfs(nums, dp) - 1)%mod;
    }
private:
    int mod = 1e9+7;
    long dfs(vector<int>& nums, vector<vector<long>>& dp) {
        if(!nums.size()) return 1;
        vector<int> left, right;
        for(int i=1; i<nums.size(); ++i) {
            if(nums[i]>nums[0]) right.push_back(nums[i]);
            else left.push_back(nums[i]);
        }
        long lt = dfs(left, dp)%mod, rt = dfs(right, dp)%mod;
        long res =lt*rt%mod;
        return res*dp[left.size()][right.size()]%mod;
    }
};