🌱 Keegan's Digital Garden

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

4 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- elements are unique and between 1-1000
- tree is not self-balancing, therefore we dont need to worry about rebalancing in the event of insertion
- return the number of combinations as modulo 10^9+7

- the root of the tree always has to be the first element in the array, as it will determine the correctness of the left and right subtrees
	- need some kind of subproblem after the base case, which would be the insertion of the root node (starting element)

🤔What Did I Struggle With?

prerequisite knowledge needed to solve this problem:
- binomial coefficient for calculating combinatorics 

also couldnt figure out the recurrence relation for this problem

💡 Explanation of Solution

1. Root Determination: the first element of the array always becomes the root of the BST, as insertion in BST starts with the first element

2. Subproblems:
	- divide the array into two parts: 
	- elements less than the root (left subtree)
	- elements greater than root (right subtree)
	- for each subtree, recursively determine the number of ways to reorder it to produce the same subtree structure

3. Combination Formula:
	- the number of ways to interleave left and right subtree elements while maintaining their relative order is determined by combinatorics 
	- if n elements are divided into 1 (left) and r (right), the formula for choosing positions is:
	- binomial coefficient formula 

4. Modulo Arithmetic:
	- Since the result needs to be modulo 10^9+7, use modular arithmetic in *all* calculations to avoid overflow

⌛ Complexity Analysis

Time Complexity: O(n log n)
	- recursive division of the array into left and right subtrees, with factorial calculations done in O(1) using precomputed values

Space Complexity: O(n^2)
	- storage for precomputed factorials and inverse factorials

💻 Implementation of Solution

class Solution {
public:
    const int MOD = 1e9 + 7; // Modulo constant for large numbers
    vector<long long> fact, invFact; // Factorial and inverse factorial arrays
 
    // Precompute factorials and inverse factorials for efficient binomial coefficient calculation
    void precomputeFactorials(int n) {
        fact.resize(n + 1, 1);
        invFact.resize(n + 1, 1);
        for (int i = 2; i <= n; ++i) {
            fact[i] = fact[i - 1] * i % MOD; // Compute factorials % MOD
        }
        invFact[n] = power(fact[n], MOD - 2); // Compute modular inverse using Fermat's Little Theorem
        for (int i = n - 1; i >= 1; --i) {
            invFact[i] = invFact[i + 1] * (i + 1) % MOD; // Compute inverse factorials
        }
    }
 
    // Fast modular exponentiation function to calculate (base^exp) % MOD
    long long power(long long base, int exp) {
        long long result = 1;
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = result * base % MOD; // Multiply when exponent bit is 1
            }
            base = base * base % MOD; // Square the base
            exp /= 2; // Shift exponent right
        }
        return result;
    }
 
    // Function to calculate binomial coefficient C(n, k) % MOD
    long long binomialCoefficient(int n, int k) {
        if (k > n) return 0; // Invalid case
        return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
    }
 
    // Recursive function to compute the number of ways to reorder the array to produce the same BST
    long long dfs(vector<int>& nums) {
        if (nums.size() <= 2) return 1; // Base case: No reordering needed
 
        // Split the array into left and right subtrees
        vector<int> left, right;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] < nums[0]) left.push_back(nums[i]);
            else right.push_back(nums[i]);
        }
 
        // Recursively calculate the number of ways for left and right subtrees
        long long leftWays = dfs(left) % MOD;
        long long rightWays = dfs(right) % MOD;
 
        // Use binomial coefficient to calculate the number of ways to interleave left and right
        long long totalWays = binomialCoefficient(nums.size() - 1, left.size());
 
        // Combine results from left and right subtrees, and return the total number of ways
        return (totalWays * leftWays % MOD) * rightWays % MOD;
    }
 
    // Main function to calculate the number of ways to reorder the array to produce the same BST
    int numOfWays(vector<int>& nums) {
        int n = nums.size();
        precomputeFactorials(n); // Precompute factorials and inverse factorials
        return (dfs(nums) - 1 + MOD) % MOD; // Subtract 1 to exclude the original order
    }
};

Graph View