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

Array Math Divide and Conquer Dynamic Programming Tree Binary Search Tree Memoization combinatorics Binary Tree

Time: O(n^2)

Space: O(n^2)

Problem Overview

Every reorder that builds the same BST must keep the same relative order inside the left subtree and inside the right subtree.

Intuition

Every reorder that builds the same BST must keep the same relative order inside the left subtree and inside the right subtree. After the root is fixed as the first element, the remaining values split into those two subsequences, and any interleaving of them that preserves each side's order is valid. The number of those interleavings is the binomial coefficient C(left + right, left), and each side multiplies by the same count computed recursively. Subtract one at the end so the given order itself is not counted.

Algorithm

1Precompute Pascal's triangle of binomial coefficients modulo 1e9+7 up to n.
2If the current sequence has length at most 2, return 1.
3Partition everything after the first value into a left array of smaller values and a right array of larger ones, keeping relative order.
4Multiply C(leftCount + rightCount, leftCount) by the recursive answers on left and right.
5At the top level return that product minus 1, reduced modulo 1e9+7.

Example Walkthrough

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

1.Root 3 sends 1,2 to the left and 5,4,6 to the right.
2.Those five later values can be interleaved in C(5,2) = 10 ways while keeping each side's order.
3.The left side of length 2 has 1 local way. The right side rooted at 5 contributes more through its own split.
4.The product of all local choices is 20, so after subtracting the original order the answer is 19.

Output: 19

Common Pitfalls

•Subtract 1 only once at the top. The recursive helper counts all orders including the current one.
•Keep relative order when building left and right. Sorting them would describe different BSTs.
•Use modular multiplication with a 64-bit temporary so the product does not overflow before the remainder.
•Pascal's triangle needs size n, because the top call asks for C(n - 1, leftCount).

1569.cs

// Approach: The BST shape is fixed by the relative order of values. After the
// root, the left and right subsequences may be interleaved in any order that
// keeps each side's relative order, which is C(left+right, left) ways, times
// the same count recursively on each side. Subtract 1 so the original order
// is not counted. Precompute binomial coefficients with Pascal's triangle.
// Time: O(n^2) Space: O(n^2)

public class Solution
{
    private const int MOD = 1_000_000_007;
    private int[][] comb;

    public int NumOfWays(int[] nums)
    {
        int n = nums.Length;
        comb = BuildComb(n);
        return (int)((Ways(nums) - 1 + MOD) % MOD);
    }

    private long Ways(int[] nums)
    {
        int n = nums.Length;
        if (n <= 2)
            return 1;

        int root = nums[0];
        int leftCount = 0;
        for (int i = 1; i < n; i++)
            if (nums[i] < root)
                leftCount++;

        int[] left = new int[leftCount];
        int[] right = new int[n - 1 - leftCount];
        int li = 0, ri = 0;
        for (int i = 1; i < n; i++)
        {
            if (nums[i] < root)
                left[li++] = nums[i];
            else
                right[ri++] = nums[i];
        }

        long ans = comb[n - 1][leftCount];
        ans = ans * Ways(left) % MOD;
        ans = ans * Ways(right) % MOD;
        return ans;
    }

    private static int[][] BuildComb(int n)
    {
        int[][] c = new int[n + 1][];
        for (int i = 0; i <= n; i++)
        {
            c[i] = new int[i + 1];
            c[i][0] = 1;
            c[i][i] = 1;
            for (int j = 1; j < i; j++)
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
        }
        return c;
    }
}

Was this solution helpful?