We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Reorder Array to Get Same BST

Number: 1692

Difficulty: Hard

Paid? No

Companies: DE Shaw, Amazon, Google

Problem Description

Given a permutation of integers from 1 to n, the task is to count the number of ways to reorder the array such that when inserted into an initially empty Binary Search Tree (BST), the resulting tree is identical in structure to the BST obtained from the original order. The answer must be returned modulo 10^9+7 and must subtract one from the computed count (since we do not count the original ordering).

Key Insights

  • The BST structure is determined by the root (first element) and the division of the remaining elements into left (smaller than the root) and right (larger than the root) subtrees.
  • The relative ordering within the left and right subarrays must be preserved.
  • The total number of valid reorderings can be calculated by choosing positions to interleave the left and right subtree elements.
  • Use recursion: compute the number of valid reorderings for each subtree and combine them using the binomial coefficient.
  • Modular arithmetic and efficient precomputation of factorials and inverses are used to handle large numbers.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case due to recursive splitting and combination computations. Space Complexity: O(n) for recursion stack and storing factorials/inverses.

Solution

We solve the problem using a divide and conquer approach with recursion:

  1. The first element of the array always becomes the root. Partition remaining elements into left (less than root) and right (greater than root).
  2. Recursively compute the number of valid reorderings for the left and right subtrees.
  3. Combine the results: the number of ways to interleave the two subtrees while preserving the internal order is given by the binomial coefficient (L+R choose L).
  4. Multiply the number of ways from the left and right subtrees with the interleaving count.
  5. Since the original array order is considered one possibility, subtract 1 from the final answer. All operations are performed modulo 10^9 + 7.
  6. Precompute factorials and inverse factorials for efficiently computing binomial coefficients.

The key data structures used are arrays (or lists) for storing the nodes and recursion for traversing the BST partitions. Modular arithmetic ensures that operations remain efficient even with large numbers.

Code Solutions

MOD = 10**9 + 7

# Precompute factorial and inverse factorial arrays.
def precompute_factorials(n, mod=MOD):
    fact = [1] * (n + 1)
    inv_fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % mod
    inv_fact[n] = pow(fact[n], mod - 2, mod)  # Fermat's little theorem
    for i in range(n, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % mod
    return fact, inv_fact

# Compute binomial coefficient C(n, k) modulo mod.
def binom(n, k, fact, inv_fact, mod=MOD):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % mod * inv_fact[n - k] % mod

# Use recursion to count the number of ways for a given list of nodes.
def dfs(nodes, fact, inv_fact):
    if len(nodes) <= 2:
        return 1
    root = nodes[0]
    left = [x for x in nodes if x < root]
    right = [x for x in nodes if x > root]
    leftWays = dfs(left, fact, inv_fact) % MOD
    rightWays = dfs(right, fact, inv_fact) % MOD
    # Total ways to interweave left and right subtrees.
    totalWays = binom(len(left) + len(right), len(left), fact, inv_fact, MOD)
    return totalWays * leftWays % MOD * rightWays % MOD

def numOfWays(nums):
    n = len(nums)
    fact, inv_fact = precompute_factorials(n, MOD)
    # Compute total ways for the full tree.
    total = dfs(nums, fact, inv_fact)
    # Subtract 1 because original ordering is not counted.
    return (total - 1) % MOD

# Example usage:
print(numOfWays([2, 1, 3]))
← Back to All Questions