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

/**
 * Problem: LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.ArrayList;
import java.util.List;

/**
 * Problem: LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    private static final long MOD = 1_000_000_007L;
    private long[][] C;

    public int numOfWays(int[] nums) {
        int n = nums.length;
        C = new long[n + 1][n + 1];
        for (int i = 0; i <= n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int x : nums) list.add(x);
        long total = ways(list);
        return (int) ((total - 1 + MOD) % MOD);
    }

    private long ways(List<Integer> list) {
        int size = list.size();
        if (size <= 2) return 1;
        int root = list.get(0);
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        for (int i = 1; i < size; i++) {
            int v = list.get(i);
            if (v < root) left.add(v);
            else right.add(v);
        }
        long res = C[size - 1][left.size()];
        res = (res * ways(left)) % MOD;
        res = (res * ways(right)) % MOD;
        return res;
    }
}

"""
Problem: LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
import math
from typing import List

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        MOD = 1_000_000_007

        def ways(arr: List[int]) -> int:
            if len(arr) <= 2:
                return 1
            root = arr[0]
            left = [x for x in arr[1:] if x < root]
            right = [x for x in arr[1:] if x > root]
            return (math.comb(len(arr) - 1, len(left)) * ways(left) * ways(right)) % MOD

        return (ways(nums) - 1) % MOD

/**
 * Problem: LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>

using namespace std;

/**
 * Problem: LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
class Solution {
private:
    static constexpr long long MOD = 1000000007LL;
    vector<vector<long long>> C;

    long long ways(const vector<int>& list) {
        int size = list.size();
        if (size <= 2) return 1;
        int root = list[0];
        vector<int> left;
        vector<int> right;
        for (int i = 1; i < size; i++) {
            if (list[i] < root) left.push_back(list[i]);
            else right.push_back(list[i]);
        }
        long long res = C[size - 1][left.size()];
        res = (res * ways(left)) % MOD;
        res = (res * ways(right)) % MOD;
        return res;
    }

public:
    int numOfWays(vector<int>& nums) {
        int n = nums.size();
        C.assign(n + 1, vector<long long>(n + 1, 0));
        for (int i = 0; i <= n; i++) {
            C[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
            }
        }
        long long total = ways(nums);
        return (total - 1 + MOD) % MOD;
    }
};

/**
 * Problem: LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
var numOfWays = function(nums) {
    const MOD = 1000000007n;
    const n = nums.length;

    const C = Array.from({ length: n + 1 }, () => new BigInt64Array(n + 1));
    for (let i = 0; i <= n; i++) {
        C[i][0] = 1n;
        for (let j = 1; j <= i; j++) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }

    function ways(arr) {
        const size = arr.length;
        if (size <= 2) return 1n;
        const root = arr[0];
        const left = [];
        const right = [];
        for (let i = 1; i < size; i++) {
            if (arr[i] < root) left.push(arr[i]);
            else right.push(arr[i]);
        }
        let res = C[size - 1][left.length];
        res = (res * ways(left)) % MOD;
        res = (res * ways(right)) % MOD;
        return res;
    }

    const total = ways(nums);
    return Number((total - 1n + MOD) % MOD);
};