Formatted question description: https://leetcode.ca/all/1569.html

1569. Number of Ways to Reorder Array to Get Same BST (Hard)

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.

Related Topics:
Dynamic Programming

Solution 1.

class Solution {
    final int MODULO = 1000000007;

    public int numOfWays(int[] nums) {
        int length = nums.length;
        int[][] combinations = calculateCombinations(length);
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < length; i++)
            list.add(nums[i]);
        int ways = getWays(list, combinations);
        return ways - 1;
    }

    public int[][] calculateCombinations(int n) {
        int[][] combinations = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            combinations[i][0] = 1;
            for (int j = 1; j <= i; j++)
                combinations[i][j] = (combinations[i - 1][j] + combinations[i - 1][j - 1]) % MODULO;
        }
        return combinations;
    }

    public int getWays(List<Integer> list, int[][] combinations) {
        if (list.isEmpty())
            return 1;
        List<Integer> leftList = new ArrayList<Integer>();
        List<Integer> rightList = new ArrayList<Integer>();
        int root = list.get(0);
        int size = list.size();
        for (int i = 1; i < size; i++) {
            int num = list.get(i);
            if (num < root)
                leftList.add(num);
            else
                rightList.add(num);
        }
        int leftWays = getWays(leftList, combinations);
        int rightWays = getWays(rightList, combinations);
        long ways = (long) combinations[size - 1][leftList.size()] * leftWays % MODULO * rightWays % MODULO;
        return (int) ways;
    }
}

############

class Solution {
    int mod = (int) 1e9 + 7;

    public int numOfWays(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        return dfs(Arrays.stream(nums).boxed().collect(Collectors.toList()), calc(nums.length)) - 1;
    }

    private int dfs(List<Integer> list, int[][] c) {
        if (list.isEmpty()) {
            return 1;
        }
        List<Integer> left
            = list.stream().filter(n -> n < list.get(0)).collect(Collectors.toList());
        List<Integer> right
            = list.stream().filter(n -> n > list.get(0)).collect(Collectors.toList());
        return (int) ((long) c[list.size() - 1][left.size()] * dfs(left, c) % mod * dfs(right, c)
            % mod);
    }

    private int[][] calc(int n) {
        int[][] c = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    c[i][j] = 1;
                } else {
                    c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
                }
            }
        }
        return c;
    }
}

// OJ: https://leetcode.com/problems/number-of-ways-to-reorder-array-to-get-same-bst/
// Time: O(N^3)
// Space: O(N^2)
class Solution {
    int mod = 1e9 + 7;
    int combination(int k, int n, int mod) {
        if (k > n - k) k = n - k;
        vector<int> dp(k + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = min(i, k); j > 0; --j) dp[j] = (dp[j] + dp[j - 1]) % mod;
        }
        return dp[k];
    }
    int dfs(vector<int> &A)  {
        if (A.size() <= 1) return 1;
        int root = A[0];
        vector<int> left, right;
        for (int i = 1; i < A.size(); ++i) {
            if (A[i] < root) left.push_back(A[i]);
            else right.push_back(A[i]);
        }
        return ((long)combination(left.size(), A.size() - 1, mod) * dfs(left)) % mod * dfs(right) % mod;
    }
public:
    int numOfWays(vector<int>& A) {
        return (dfs(A) - 1 + mod) % mod;
    }
};

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        def dfs(nums):
            if len(nums) < 2:
                return 1
            left = [x for x in nums if x < nums[0]]
            right = [x for x in nums if x > nums[0]]
            m, n = len(left), len(right)
            a, b = dfs(left), dfs(right)
            return (((c[m + n][m] * a) % mod) * b) % mod

        n = len(nums)
        mod = 10**9 + 7
        c = [[0] * n for _ in range(n)]
        c[0][0] = 1
        for i in range(1, n):
            c[i][0] = 1
            for j in range(1, i + 1):
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod
        return (dfs(nums) - 1 + mod) % mod

func numOfWays(nums []int) int {
	n := len(nums)
	const mod = 1e9 + 7
	c := make([][]int, n)
	for i := range c {
		c[i] = make([]int, n)
	}
	c[0][0] = 1
	for i := 1; i < n; i++ {
		c[i][0] = 1
		for j := 1; j <= i; j++ {
			c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod
		}
	}
	var dfs func(nums []int) int
	dfs = func(nums []int) int {
		if len(nums) < 2 {
			return 1
		}
		var left, right []int
		for _, x := range nums[1:] {
			if x < nums[0] {
				left = append(left, x)
			} else {
				right = append(right, x)
			}
		}
		m, n := len(left), len(right)
		a, b := dfs(left), dfs(right)
		return c[m+n][m] * a % mod * b % mod
	}
	return (dfs(nums) - 1 + mod) % mod
}

function numOfWays(nums: number[]): number {
    const n = nums.length;
    const mod = 1e9 + 7;
    const c = new Array(n).fill(0).map(() => new Array(n).fill(0));
    c[0][0] = 1;
    for (let i = 1; i < n; ++i) {
        c[i][0] = 1;
        for (let j = 1; j <= i; ++j) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
        }
    }
    const dfs = (nums: number[]): number => {
        if (nums.length < 2) {
            return 1;
        }
        const left: number[] = [];
        const right: number[] = [];
        for (let i = 1; i < nums.length; ++i) {
            if (nums[i] < nums[0]) {
                left.push(nums[i]);
            } else {
                right.push(nums[i]);
            }
        }
        const m = left.length;
        const n = right.length;
        const a = dfs(left);
        const b = dfs(right);
        return Number(
            (BigInt(c[m + n][m]) * BigInt(a) * BigInt(b)) % BigInt(mod),
        );
    };
    return (dfs(nums) - 1 + mod) % mod;
}

1569 - Number of Ways to Reorder Array to Get Same BST

1569. Number of Ways to Reorder Array to Get Same BST (Hard)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1569. Number of Ways to Reorder Array to Get Same BST (Hard)

Solution 1.

All Problems

All Solutions