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

Problem Description

Given an array nums representing a permutation of integers from 1 to n, construct a Binary Search Tree (BST) by inserting elements of nums in order. The task is to find the number of different ways to reorder nums such that the constructed BST remains identical to the one formed from the original array. The answer might be large, so it should be returned modulo 109 + 7.

Solution: Combination Counting + Recursion

This problem can be efficiently solved using a recursive approach combined with combinatorial calculations. The core idea is to leverage the properties of BSTs:

1. Root: The first element in any valid ordering will always be the root of the BST.
2. Subtrees: Elements smaller than the root form the left subtree, and elements larger than the root form the right subtree. These subtrees are independent BSTs themselves.

The recursive function dfs(nums) calculates the number of ways to reorder the input array nums such that the resulting BST is identical.

• Base Case: If nums has fewer than 2 elements, there's only 1 way (itself).
• Recursive Step:
  • Partition nums into left (elements < root) and right (elements > root).
  • Recursively calculate the number of ways for left and right subtrees: a = dfs(left) and b = dfs(right).
  • The total number of ways is the product of:
    • The number of ways to arrange elements in the left and right subtrees (a * b).
    • The number of ways to choose positions for the left subtree elements among all the elements (excluding the root). This is given by the binomial coefficient C(m+n, m), where m is the size of left and n is the size of right. This coefficient represents the number of ways to choose m positions out of m+n total positions.

The binomial coefficient C(m+n, m) is pre-calculated using Pascal's triangle to improve efficiency. We use dynamic programming to compute these coefficients, avoiding redundant computations.

Finally, the result is dfs(nums) - 1 (because the original ordering is already counted), taken modulo 109 + 7.

Time and Space Complexity

• Time Complexity: O(n2) due to the recursive nature of the dfs function and the pre-computation of binomial coefficients. The recursion explores all possible combinations.
• Space Complexity: O(n2) primarily due to the storage of pre-computed binomial coefficients. The recursion depth can also reach O(n) in the worst case (a skewed BST).

Code (Python)

class Solution:
    def numOfWays(self, nums: List[int]) -> int:
        n = len(nums)
        mod = 10**9 + 7
        c = [[0] * n for _ in range(n)]
        c[0][0] = 1
        for i in range(1, n):
            c[i][0] = 1
            for j in range(1, i + 1):
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod
 
        def dfs(nums):
            if len(nums) < 2:
                return 1
            left = [x for x in nums if x < nums[0]]
            right = [x for x in nums if x > nums[0]]
            m, n = len(left), len(right)
            a, b = dfs(left), dfs(right)
            return (((c[m + n][m] * a) % mod) * b) % mod
 
        return (dfs(nums) - 1 + mod) % mod

The code in other languages (Java, C++, Go, TypeScript) follows a very similar structure, with the main differences lying in syntax and data structure handling. The core logic of recursion and binomial coefficient calculation remains consistent across all implementations.