Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1569. Number of Ways to Reorder Array to Get Same BST - Leetcode Solution

Code Implementation

from math import comb
from functools import lru_cache

class Solution:
    def numOfWays(self, nums):
        MOD = 10 ** 9 + 7

        @lru_cache(None)
        def helper(arr):
            if len(arr) <= 2:
                return 1
            left = tuple(x for x in arr if x < arr[0])
            right = tuple(x for x in arr if x > arr[0])
            return comb(len(arr)-1, len(left)) * helper(left) * helper(right) % MOD

        return (helper(tuple(nums)) - 1) % MOD
    
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
    const int MOD = 1e9 + 7;
    vector<vector<long long>> comb;
    
    void buildComb(int n) {
        comb.assign(n+1, vector<long long>(n+1, 0));
        for (int i = 0; i <= n; ++i) {
            comb[i][0] = comb[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
            }
        }
    }
    
    long long dfs(vector<int> &arr) {
        int n = arr.size();
        if (n <= 2) return 1;
        vector<int> left, right;
        for (int i = 1; i < n; ++i) {
            if (arr[i] < arr[0]) left.push_back(arr[i]);
            else right.push_back(arr[i]);
        }
        long long l = dfs(left) % MOD;
        long long r = dfs(right) % MOD;
        return comb[n-1][left.size()] * l % MOD * r % MOD;
    }
    
public:
    int numOfWays(vector<int>& nums) {
        int n = nums.size();
        buildComb(n);
        return (dfs(nums) - 1 + MOD) % MOD;
    }
};
    
import java.util.*;

class Solution {
    static final int MOD = 1_000_000_007;
    long[][] comb;

    void buildComb(int n) {
        comb = new long[n+1][n+1];
        for (int i = 0; i <= n; ++i) {
            comb[i][0] = comb[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
            }
        }
    }

    long dfs(List<Integer> arr) {
        int n = arr.size();
        if (n <= 2) return 1;
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        for (int i = 1; i < n; ++i) {
            if (arr.get(i) < arr.get(0)) left.add(arr.get(i));
            else right.add(arr.get(i));
        }
        long l = dfs(left) % MOD;
        long r = dfs(right) % MOD;
        return comb[n-1][left.size()] * l % MOD * r % MOD;
    }

    public int numOfWays(int[] nums) {
        int n = nums.length;
        buildComb(n);
        List<Integer> arr = new ArrayList<>();
        for (int x : nums) arr.add(x);
        return (int)((dfs(arr) - 1 + MOD) % MOD);
    }
}
    
var numOfWays = function(nums) {
    const MOD = 1e9 + 7;
    const n = nums.length;
    let comb = Array.from({length: n+1}, () => Array(n+1).fill(0));
    for (let i = 0; i <= n; ++i) {
        comb[i][0] = comb[i][i] = 1;
        for (let j = 1; j < i; ++j) {
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
        }
    }

    function dfs(arr) {
        if (arr.length <= 2) return 1;
        let left = [], right = [];
        for (let i = 1; i < arr.length; ++i) {
            if (arr[i] < arr[0]) left.push(arr[i]);
            else right.push(arr[i]);
        }
        let l = dfs(left) % MOD;
        let r = dfs(right) % MOD;
        return comb[arr.length-1][left.length] * l % MOD * r % MOD;
    }

    return (dfs(nums) - 1 + MOD) % MOD;
};

Problem Description

Given an array nums that represents the insertion order of nodes into a binary search tree (BST), you are asked to compute the number of different reorderings of nums (excluding the original order) that, when inserted into an empty BST, would result in a BST with exactly the same structure as the original one built from nums. Each element in nums is unique, and you must not reuse elements. The answer should be returned modulo 10^9 + 7.

Thought Process

To solve this problem, we need to count how many different ways we can reorder the array so that, when constructing the BST by inserting elements from left to right, the tree structure remains unchanged. A brute-force approach would try all permutations, but this is computationally infeasible for larger arrays. Instead, we look for patterns in how BSTs are built, and realize that the relative order among left and right subtrees must be preserved for the BST structure to remain the same. This leads us to think recursively and use combinatorics to efficiently count the valid reorderings.

Solution Approach

The solution is based on recursion and combinatorics:
  • Step 1: The first element of nums is always the root of the BST. All elements less than the root go to the left subtree; all greater go to the right subtree.
  • Step 2: The problem reduces to recursively counting the number of reorderings for the left and right subtrees, and then combining them.
  • Step 3: Since the order among elements in the left and right subtrees must be preserved, but their positions can be interleaved, we use the binomial coefficient C(n, k) to count the number of ways to merge the left and right sequences, where n is the total number of elements (excluding the root), and k is the number of left subtree elements.
  • Step 4: The answer for the current subtree is C(n, k) * leftWays * rightWays, where leftWays and rightWays are the recursive answers for the left and right subtrees.
  • Step 5: The recursion stops when the subtree has 0, 1, or 2 nodes, since only one BST structure can be formed in those cases.
  • Step 6: Since the numbers can be large, we precompute binomial coefficients up to n using Pascal's Triangle or use a function like math.comb in Python.
  • Step 7: Finally, since the problem asks for the number of reorderings excluding the original order, we subtract 1 from the result.

Example Walkthrough

Consider nums = [2,1,3]:

  • First, insert 2 (root). 1 goes to the left, 3 goes to the right.
  • Left subtree: [1] (only one node, so only one way)
  • Right subtree: [3] (only one node, so only one way)
  • To interleave left and right subtrees, we have 2 elements: 1 and 3. The number of ways to arrange them while preserving their relative order is C(2,1) = 2.
  • So, total ways = 2 * 1 * 1 = 2
  • Subtract the original order ([2,1,3]), so the answer is 1.
  • The only other valid order is [2,3,1], which also produces the same BST.

Time and Space Complexity

  • Brute-force: Trying all permutations is O(n!), which is not feasible for even moderate n.
  • Optimized (Recursive with memoization): For each subtree, the work done is proportional to the number of nodes, and the number of unique subproblems is limited by the structure of the tree. With memoization, the complexity is O(n^2) for precomputing binomial coefficients and O(2^n) for all possible subtree splits, but in practice, it's much faster due to pruning and caching.
  • Space Complexity: O(n^2) for storing binomial coefficients and memoization cache.

Summary

The key insight is that the BST structure is determined by the relative ordering of elements. By recursively breaking the problem into left and right subtrees and using combinatorics to count the ways to interleave them, we avoid brute-force enumeration. Precomputing binomial coefficients and using memoization makes the solution efficient and elegant. This approach beautifully combines recursion, combinatorics, and dynamic programming to solve a complex-looking problem in a manageable way.