Number of Ways to Reorder Array to Get Same BST Problem

Problem

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.

Examples

Example 1:

1
2
3
4
5


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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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:

1
2
3
4
5


Input:
nums = [1,2,3]
Output:
 0
Explanation: There are no other orderings of nums that will yield the same BST.

Solution

Method 1 – Divide and Conquer + Combinatorics

Intuition

The number of ways to reorder the array to get the same BST is determined by the number of ways to interleave left and right subtrees, which is a combinatorial problem.

Approach

Precompute binomial coefficients (combinations) for all possible sizes.
Recursively split the array into left and right subtrees, and compute the number of ways for each subtree.
The total number of ways is the product of ways for left and right subtrees, multiplied by the number of ways to interleave them.
Subtract 1 from the final answer to exclude the original ordering.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    int MOD = 1e9+7;
    vector<vector<int>> comb;
    int dfs(vector<int>& nums) {
        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]);
        }
        int l = dfs(left), r = dfs(right);
        return (long long)comb[n-1][left.size()] * l % MOD * r % MOD;
    }
public:
    int numOfWays(vector<int>& nums) {
        int n = nums.size();
        comb.assign(n+1, vector<int>(n+1, 0));
        for (int i = 0; i <= n; ++i) {
            comb[i][0] = comb[i][i] = 1;
            for (int j = 1; j < i; ++j)
                comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
        }
        return (dfs(nums) - 1 + MOD) % MOD;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func numOfWays(nums []int) int {
    mod := int(1e9+7)
    n := len(nums)
    comb := make([][]int, n+1)
    for i := range comb {
        comb[i] = make([]int, n+1)
        comb[i][0], comb[i][i] = 1, 1
        for j := 1; j < i; j++ {
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % mod
        }
    }
    var dfs func([]int) int
    dfs = func(arr []int) int {
        if len(arr) <= 2 { return 1 }
        left, right := []int{}, []int{}
        for _, v := range arr[1:] {
            if v < arr[0] { left = append(left, v) } else { right = append(right, v) }
        }
        l, r := dfs(left), dfs(right)
        return comb[len(arr)-1][len(left)] * l % mod * r % mod
    }
    return (dfs(nums) - 1 + mod) % mod
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    int MOD = 1_000_000_007;
    int[][] comb;
    public int numOfWays(int[] nums) {
        int n = nums.length;
        comb = new int[n+1][n+1];
        for (int i = 0; i <= n; ++i) {
            comb[i][0] = comb[i][i] = 1;
            for (int j = 1; j < i; ++j)
                comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
        }
        return (dfs(nums) - 1 + MOD) % MOD;
    }
    private int dfs(int[] nums) {
        int n = nums.length;
        if (n <= 2) return 1;
        List<Integer> left = new ArrayList<>(), right = new ArrayList<>();
        for (int i = 1; i < n; ++i) {
            if (nums[i] < nums[0]) left.add(nums[i]);
            else right.add(nums[i]);
        }
        int l = dfs(left.stream().mapToInt(i->i).toArray());
        int r = dfs(right.stream().mapToInt(i->i).toArray());
        return (int)((long)comb[n-1][left.size()] * l % MOD * r % MOD);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    val MOD = 1_000_000_007
    lateinit var comb: Array<IntArray>
    fun numOfWays(nums: IntArray): Int {
        val n = nums.size
        comb = Array(n+1) { IntArray(n+1) }
        for (i in 0..n) {
            comb[i][0] = 1; comb[i][i] = 1
            for (j in 1 until i)
                comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD
        }
        return (dfs(nums) - 1 + MOD) % MOD
    }
    fun dfs(nums: IntArray): Int {
        val n = nums.size
        if (n <= 2) return 1
        val left = mutableListOf<Int>()
        val right = mutableListOf<Int>()
        for (i in 1 until n) {
            if (nums[i] < nums[0]) left.add(nums[i]) else right.add(nums[i])
        }
        val l = dfs(left.toIntArray())
        val r = dfs(right.toIntArray())
        return (comb[n-1][left.size] * l.toLong() % MOD * r % MOD).toInt()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def numOfWays(self, nums: list[int]) -> int:
        from math import comb as C
        MOD = 10**9+7
        def dfs(arr):
            if len(arr) <= 2: return 1
            left = [x for x in arr[1:] if x < arr[0]]
            right = [x for x in arr[1:] if x > arr[0]]
            return C(len(arr)-1, len(left)) * dfs(left) % MOD * dfs(right) % MOD
        return (dfs(nums) - 1) % MOD

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


impl Solution {
    pub fn num_of_ways(nums: Vec<i32>) -> i32 {
        fn comb(n: usize, k: usize, memo: &mut Vec<Vec<i32>>) -> i32 {
            if k == 0 || k == n { return 1; }
            if memo[n][k] != 0 { return memo[n][k]; }
            memo[n][k] = (comb(n-1, k-1, memo) + comb(n-1, k, memo)) % 1_000_000_007;
            memo[n][k]
        }
        fn dfs(nums: &[i32], memo: &mut Vec<Vec<i32>>) -> i32 {
            let n = nums.len();
            if n <= 2 { return 1; }
            let left: Vec<i32> = nums[1..].iter().cloned().filter(|&x| x < nums[0]).collect();
            let right: Vec<i32> = nums[1..].iter().cloned().filter(|&x| x > nums[0]).collect();
            let l = dfs(&left, memo);
            let r = dfs(&right, memo);
            let c = comb(n-1, left.len(), memo);
            ((c as i64 * l as i64 % 1_000_000_007 * r as i64 % 1_000_000_007) as i32)
        }
        let n = nums.len();
        let mut memo = vec![vec![0; n+1]; n+1];
        ((dfs(&nums, &mut memo) - 1 + 1_000_000_007) % 1_000_000_007)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    numOfWays(nums: number[]): number {
        const MOD = 1e9+7;
        const n = nums.length;
        const comb: number[][] = Array.from({length: n+1}, () => Array(n+1).fill(0));
        for (let i = 0; i <= n; ++i) {
            comb[i][0] = comb[i][i] = 1;
            for (let j = 1; j < i; ++j)
                comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
        }
        function dfs(arr: number[]): number {
            if (arr.length <= 2) return 1;
            const left = arr.slice(1).filter(x => x < arr[0]);
            const right = arr.slice(1).filter(x => x > arr[0]);
            return comb[arr.length-1][left.length] * dfs(left) % MOD * dfs(right) % MOD;
        }
        return (dfs(nums) - 1 + MOD) % MOD;
    }
}

Complexity

⏰ Time complexity: O(n^2) (due to binomial coefficient computation and recursion)
🧺 Space complexity: O(n^2) (for memoization of combinations)

Number of Ways to Reorder Array to Get Same BST Problem#

Problem#

Examples#

Solution#

Method 1 – Divide and Conquer + Combinatorics#

Intuition#

Approach#

Code#

Complexity#