Number of Ways to Reorder Array to Get Same BST — Hard Problem & Solution

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

Difficulty: Hard
Topics: Arrays, Math, Dynamic Programming, Divide and Conquer, Combinatorics
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

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

Build Pascal's triangle up to n for the binomials.
Recursively: a sequence of length at most 2 has exactly one arrangement.
Otherwise split on the first element, and return C(len-1, |left|) · count(left) · count(right).
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue