Number of Ways to Reorder Array to Get Same BST

Hard
1094.

Number of Ways to Reorder Array to Get Same BST

Number of Ways to Reorder Array to Get Same BST is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Meta interviews.

nums is a permutation of distinct integers. Inserting them left to right into an empty binary search tree produces some tree.

Return the number of other orderings of nums that produce the identical tree, modulo 10⁹ + 7.

Example 1

Input
nums = [2,1,3]
Output
1
Explanation
`[2,3,1]` builds the same tree.

Example 2

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

Example 3

Input
nums = [1,2,3]
Output
0
Explanation
The tree is a right chain, so the order is forced.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= nums.length
  • All integers in nums are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var numOfWays = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Ways to Reorder Array to Get Same BST — Solution

Number of Ways to Reorder Array to Get Same BST solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Number of Ways to Reorder Array to Get Same BST is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Meta interviews.

Problem statement

nums is a permutation of distinct integers. Inserting them left to right into an empty binary search tree produces some tree.

Return the number of other orderings of nums that produce the identical tree, modulo 10⁹ + 7.

Example 1

Input: nums = [2,1,3]
Output: 1
Explanation: `[2,3,1]` builds the same tree.

Example 2

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

Example 3

Input: nums = [1,2,3]
Output: 0
Explanation: The tree is a right chain, so the order is forced.

Constraints

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

Hints for Number of Ways to Reorder Array to Get Same BST

  1. Hint 1

    The first element must stay first — it is the root.

  2. Hint 2

    The elements smaller than the root form the left subtree, the rest the right, and their relative orders are each fixed independently.

  3. Hint 3

    So the count is C(n-1, leftSize) times the counts for the two subtrees.

How to solve Number of Ways to Reorder Array to Get Same BST

Recursive counting. The root is forced to come first. The remaining n - 1 elements split into the left and right subtrees, and any interleaving of the two sequences produces the same tree — C(n-1, |left|) of them — while the internal order of each side is counted recursively. Subtract 1 at the end to exclude the original ordering.

Approach

  1. Build Pascal's triangle up to n for the binomials.
  2. Recursively: a sequence of length at most 2 has exactly one arrangement.
  3. Otherwise split on the first element, and return C(len-1, |left|) · count(left) · count(right).
  4. Return count(nums) - 1 modulo 10⁹ + 7.

Why it works

Interleaving is free because insertion into a BST routes each value by comparison with the root — a left-subtree value and a right-subtree value never interact, so their relative order between the two groups is irrelevant. Building the binomials with Pascal's triangle sidesteps modular inverses entirely, which at n <= 1000 costs a megabyte of additions and nothing else.

Complexity

  • Time — O(n²)
  • Space — O(n²)

Pitfalls

  • The answer excludes the original ordering, hence the - 1.
  • That subtraction can go negative under the modulus — add the modulus back.
  • Multiplying two residues near 10⁹ needs 64-bit arithmetic, or a split multiply in JavaScript.

Reference solution

Python

from math import comb
from typing import List

def numOfWays(nums: List[int]) -> int:
    MOD = 10**9 + 7

    def count(seq: List[int]) -> int:
        if len(seq) <= 2:
            return 1
        root = seq[0]
        left = [v for v in seq[1:] if v < root]
        right = [v for v in seq[1:] if v > root]
        return comb(len(seq) - 1, len(left)) * count(left) % MOD * count(right) % MOD

    return (count(nums) - 1) % MOD

Java

public static int numOfWays(int[] nums) {
    final long MOD = 1000000007L;
    int n = nums.length;
    long[][] binom = new long[n + 1][];
    for (int i = 0; i <= n; i++) {
        binom[i] = new long[i + 1];
        Arrays.fill(binom[i], 1);
        for (int j = 1; j < i; j++) binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
    }
    List<Integer> seq = new ArrayList<>();
    for (int v : nums) seq.add(v);
    long total = nowCount(seq, binom, MOD);
    return (int) ((total - 1 + MOD) % MOD);
}

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

C++

static long long nowCount(vector<int>& seq, vector<vector<long long>>& binom, long long MOD) {
    if (seq.size() <= 2) return 1;
    int root = seq[0];
    vector<int> left, right;
    for (size_t i = 1; i < seq.size(); i++) {
        if (seq[i] < root) left.push_back(seq[i]);
        else right.push_back(seq[i]);
    }
    long long ways = binom[seq.size() - 1][left.size()];
    ways = ways * nowCount(left, binom, MOD) % MOD;
    ways = ways * nowCount(right, binom, MOD) % MOD;
    return ways;
}

int numOfWays(vector<int>& nums) {
    const long long MOD = 1000000007LL;
    int n = (int) nums.size();
    vector<vector<long long>> binom(n + 1);
    for (int i = 0; i <= n; i++) {
        binom[i].assign(i + 1, 1);
        for (int j = 1; j < i; j++) binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
    }
    vector<int> seq = nums;
    long long total = nowCount(seq, binom, MOD);
    return (int) ((total - 1 + MOD) % MOD);
}

JavaScript

var numOfWays = function(nums) {
    var MOD = 1000000007;
    var n = nums.length, i, j;
    var mulmod = function(a, b) {
        var hi = Math.floor(a / 65536), lo = a % 65536;
        return ((hi * b % MOD) * 65536 + lo * b) % MOD;
    };
    var binom = [];
    for (i = 0; i <= n; i++) {
        var row = [];
        for (j = 0; j <= i; j++) row.push(1);
        for (j = 1; j < i; j++) row[j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % MOD;
        binom.push(row);
    }
    var count = function(seq) {
        if (seq.length <= 2) return 1;
        var root = seq[0];
        var left = [], right = [];
        for (var t = 1; t < seq.length; t++) {
            if (seq[t] < root) left.push(seq[t]); else right.push(seq[t]);
        }
        var ways = binom[seq.length - 1][left.length];
        ways = mulmod(ways, count(left));
        ways = mulmod(ways, count(right));
        return ways;
    };
    return (count(nums) - 1 + MOD) % MOD;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming