Number of Ways to Reorder Array to Get Same BST

Hard

#1444Time: O(N^2). The recursive function `countWays` is called on lists of decreasing sizes. For a list of size `k`, it performs `O(k)` work to partition it. The recurrence relation for the time complexity is `T(n) = T(k) + T(n-1-k) + O(n)`, which solves to `O(n^2)` in the worst case (skewed tree). Precomputing combinations also takes `O(N^2)`.Space: O(N^2). The recursion depth can be up to `O(N)`. At each level, new lists are created for subproblems. The total size of lists stored on the recursion stack can be `O(N^2)` in the worst case (a skewed tree). The `combinations` table also requires `O(N^2)` space.1 company

Patterns

Math Dynamic Programming Combinatorics Memoization

Algorithms

Divide and Conquer Union Find

Data structures

Array Tree Binary Tree Binary Search Tree

Companies

DE Shaw

Prompt

Given an array nums that represents a permutation of integers from 1 to n. We are going to construct a binary search tree (BST) by inserting the elements of nums in order into an initially empty BST. Find the number of different ways to reorder nums so that the constructed BST is identical to that formed from the original array nums.

For example, given nums = [2,1,3], we will have 2 as the root, 1 as a left child, and 3 as a right child. The array [2,3,1] also yields the same BST but [3,2,1] yields a different BST.

Return the number of ways to reorder nums such that the BST formed is identical to the original BST formed from nums.

Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [2,1,3]
Output: 1
Explanation: We can reorder nums to be [2,3,1] which will yield the same BST. There are no other ways to reorder nums which will yield the same BST.

Example 2:

Input: nums = [3,4,5,1,2]
Output: 5
Explanation: The following 5 arrays will yield the same BST: 
[3,1,2,4,5]
[3,1,4,2,5]
[3,1,4,5,2]
[3,4,1,2,5]
[3,4,1,5,2]

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: There are no other orderings of nums that will yield the same BST.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= nums.length
All integers in nums are distinct.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a direct divide-and-conquer strategy. The number of valid reorderings for a sequence nums is determined by its root (nums[0]) and the elements forming its left and right subtrees. We can recursively calculate the number of ways for the left and right subtrees and combine the results. The key insight is that the elements of the left and right subtrees can be interleaved in any way, as long as their internal relative order is preserved. The number of ways to interleave them is given by a binomial coefficient, which we can precompute.

Algorithm

Main Idea: Use a recursive function countWays(nums) that calculates the number of valid permutations for a sequence nums representing a subtree.
Base Case: If nums has 2 or fewer elements, there's only one way to form the BST. Return 1.
Recursive Step:
1. The first element, nums[0], is the root of the current subtree.
2. Partition the remaining elements of nums into two new lists: leftNodes (elements < root) and rightNodes (elements > root), preserving their relative order.
3. Recursively call countWays(leftNodes) and countWays(rightNodes) to get the number of arrangements for the subtrees.
4. The number of ways to interleave the left and right subtree sequences is given by the binomial coefficient C(leftNodes.size() + rightNodes.size(), leftNodes.size()).
5. The total ways for the current nums is (C(...) * leftWays * rightWays) % MOD.
Combinations: Precompute binomial coefficients C(n, k) using Pascal's triangle and store them in a 2D array.
Final Result: The main function calls countWays on the initial array and subtracts 1 from the result (to exclude the original ordering).

Walkthrough

The core of this method is a recursive function, let's call it countWays(nums), which computes the total number of valid permutations for a given sequence nums that forms a specific BST structure.

The base case for the recursion is when the input list nums has a size of 2 or less. In such cases, the structure is fixed, and there's only one way to arrange the elements, so we return 1.

For a list with more than two elements, the first element nums[0] will always be the root of the BST formed by this sequence. We then iterate through the rest of the list (nums[1:]) and partition the elements into two new lists: leftNodes for all elements smaller than the root, and rightNodes for all elements larger than the root. It's crucial that this partitioning preserves the original relative order of elements within each new list.

The problem then breaks down into three parts: arranging the left subtree, arranging the right subtree, and interleaving these two arrangements. The number of ways to arrange the left and right subtrees are found by recursively calling countWays(leftNodes) and countWays(rightNodes).

The number of ways to interleave the two sequences of nodes (for the left and right subtrees) is a classic combinatorial problem. If leftNodes has size L and rightNodes has size R, we have L+R total positions to fill. We need to choose L of these positions for the leftNodes elements. This can be done in C(L+R, L) ways. We can precompute these combination values using Pascal's triangle.

The total number of ways for the current nums is the product of these three values: C(L+R, L) * countWays(leftNodes) * countWays(rightNodes), all taken modulo 10^9 + 7.

Finally, the main function calls countWays with the initial nums array and subtracts 1 from the result, as the problem asks for the number of other reorderings that produce the same BST.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    long[][] combinations;6    long MOD = 1_000_000_007;7 8    public int numOfWays(int[] nums) {9        int n = nums.length;10        List<Integer> arr = new ArrayList<>();11        for (int num : nums) {12            arr.add(num);13        }14 15        // Precompute combinations using Pascal's triangle16        combinations = new long[n + 1][n + 1];17        for (int i = 0; i <= n; i++) {18            combinations[i][0] = 1;19            for (int j = 1; j <= i; j++) {20                combinations[i][j] = (combinations[i - 1][j - 1] + combinations[i - 1][j]) % MOD;21            }22        }23 24        long totalWays = countWays(arr);25        // The problem asks for the number of ways to reorder, which is total ways - 126        return (int) ((totalWays - 1 + MOD) % MOD);27    }28 29    private long countWays(List<Integer> nums) {30        if (nums.size() <= 2) {31            return 1;32        }33 34        int rootVal = nums.get(0);35        List<Integer> leftSubtree = new ArrayList<>();36        List<Integer> rightSubtree = new ArrayList<>();37 38        for (int i = 1; i < nums.size(); i++) {39            if (nums.get(i) < rootVal) {40                leftSubtree.add(nums.get(i));41            } else {42                rightSubtree.add(nums.get(i));43            }44        }45 46        long leftWays = countWays(leftSubtree);47        long rightWays = countWays(rightSubtree);48 49        int leftSize = leftSubtree.size();50        int rightSize = rightSubtree.size();51 52        long interleavingWays = combinations[leftSize + rightSize][leftSize];53        54        long result = (interleavingWays * leftWays) % MOD;55        result = (result * rightWays) % MOD;56 57        return result;58    }59}

Complexity

Time

O(N^2). The recursive function `countWays` is called on lists of decreasing sizes. For a list of size `k`, it performs `O(k)` work to partition it. The recurrence relation for the time complexity is `T(n) = T(k) + T(n-1-k) + O(n)`, which solves to `O(n^2)` in the worst case (skewed tree). Precomputing combinations also takes `O(N^2)`.

Space

O(N^2). The recursion depth can be up to `O(N)`. At each level, new lists are created for subproblems. The total size of lists stored on the recursion stack can be `O(N^2)` in the worst case (a skewed tree). The `combinations` table also requires `O(N^2)` space.

Trade-offs

Pros

Conceptually simple and directly models the recursive nature of the problem.
Easy to implement.

Cons

High space complexity (O(N^2)) due to creating new lists at each recursive call.
The overhead of list creation and copying can make it slower in practice than other O(N^2) solutions.

This approach improves upon the pure recursive one by separating the problem into two distinct phases. First, we explicitly construct the Binary Search Tree from the input array nums. This step determines the fixed structure of the tree. Second, we perform a single post-order traversal on the constructed BST. During the traversal, we calculate the size of each subtree and use this information along with precomputed combination values to find the number of valid reorderings for that subtree. This avoids the expensive creation of new lists at each step of the recursion.

Algorithm

Phase 1: Build BST
1. Define a Node class for the BST nodes.
2. Create the BST by inserting elements from the input nums array one by one, starting with nums[0] as the root.
Phase 2: Count Ways via Traversal
1. Precompute binomial coefficients C(n, k). This can be done with an O(N^2) Pascal's triangle or, more efficiently for space, with O(N) precomputation of factorials and their modular inverses.
2. Implement a recursive traversal function, dfs(node), that returns a pair: {subtree_size, ways_for_subtree}.
3. Base Case: For a null node, dfs returns {size: 0, ways: 1}.
4. Recursive Step: For a non-null node, call dfs on its left and right children to get (leftSize, leftWays) and (rightSize, rightWays).
5. Calculate the results for the current node: totalSize = 1 + leftSize + rightSize and totalWays = C(leftSize + rightSize, leftSize) * leftWays * rightWays % MOD.
6. Return {totalSize, totalWays}.
Final Result: Call dfs(root) and subtract 1 from the returned number of ways.

Walkthrough

This method is more structured and generally more efficient, especially in terms of space. It works in two main phases.

Phase 1: Build the BST First, we determine the exact structure of the BST. We define a simple Node class and build the tree by inserting each element from the nums array in the given order. nums[0] becomes the root, and subsequent elements are inserted based on standard BST rules. This construction takes O(N^2) in the worst case (for a skewed tree) but O(N log N) on average.

Phase 2: Traverse and Count Once the tree is built, its structure is fixed. We can now traverse it to count the number of ways. We use a recursive helper function, say dfs(node), which performs a post-order traversal. This function is designed to return a pair of values for the subtree rooted at node: the total number of nodes in that subtree, and the number of ways to reorder the elements of that subtree to form the same structure.

The base case is a null node, which represents an empty subtree. It has a size of 0 and there is 1 way to arrange it (the empty arrangement).

For any given node, dfs first recursively calls itself on the left and right children. This gives us the sizes and way counts for the left and right subtrees, say (leftSize, leftWays) and (rightSize, rightWays). The total number of nodes in the current subtree is 1 + leftSize + rightSize. The number of ways to reorder the elements of this subtree is calculated using the same combinatorial formula as before: C(leftSize + rightSize, leftSize) * leftWays * rightWays. The binomial coefficients C(n, k) are precomputed.

The dfs call on the root of the entire BST will yield the total number of permutations that form the identical tree. We subtract 1 from this total to get the final answer.

This approach is more space-efficient because we are not creating copies of lists. The space for the BST and recursion stack is O(N), and if we use factorials to compute combinations, the total space complexity can be O(N).

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    static class Node {6        int val;7        Node left, right;8        Node(int v) { val = v; }9    }10 11    // A pair to return both size and ways from the recursive helper12    static class Pair {13        int size;14        long ways;15        Pair(int s, long w) { size = s; ways = w; }16    }17 18    long[][] combinations;19    long MOD = 1_000_000_007;20 21    public int numOfWays(int[] nums) {22        int n = nums.length;23        if (n <= 2) return 0;24 25        // Phase 1: Build BST26        Node root = new Node(nums[0]);27        for (int i = 1; i < n; i++) {28            insert(root, nums[i]);29        }30 31        // Precompute combinations table32        combinations = new long[n + 1][n + 1];33        for (int i = 0; i <= n; i++) {34            combinations[i][0] = 1;35            for (int j = 1; j <= i; j++) {36                combinations[i][j] = (combinations[i - 1][j - 1] + combinations[i - 1][j]) % MOD;37            }38        }39 40        // Phase 2: Traverse and count ways41        Pair result = countWays(root);42        return (int)((result.ways - 1 + MOD) % MOD);43    }44 45    private void insert(Node node, int val) {46        while (true) {47            if (val < node.val) {48                if (node.left == null) {49                    node.left = new Node(val);50                    return;51                }52                node = node.left;53            } else {54                if (node.right == null) {55                    node.right = new Node(val);56                    return;57                }58                node = node.right;59            }60        }61    }62 63    private Pair countWays(Node node) {64        if (node == null) {65            return new Pair(0, 1L); // {size, ways}66        }67 68        Pair leftResult = countWays(node.left);69        Pair rightResult = countWays(node.right);70 71        int leftSize = leftResult.size;72        int rightSize = rightResult.size;73        long leftWays = leftResult.ways;74        long rightWays = rightResult.ways;75 76        int totalSize = leftSize + rightSize + 1;77        78        long interleavingWays = combinations[leftSize + rightSize][leftSize];79        80        long totalWays = (interleavingWays * leftWays) % MOD;81        totalWays = (totalWays * rightWays) % MOD;82 83        return new Pair(totalSize, totalWays);84    }85}

Complexity

Time

O(N^2). Building the BST takes `O(N^2)` in the worst case (e.g., for a sorted `nums` array). The traversal to count ways takes `O(N)`. Precomputing combinations takes `O(N^2)`. The total time is dominated by the BST construction and combinations precomputation.

Space

O(N^2). The BST requires `O(N)` space. The recursion stack for traversal takes `O(N)` in the worst case. The `combinations` table using Pascal's triangle takes `O(N^2)` space. Note: This can be optimized to `O(N)` space by precomputing factorials and their modular inverses instead of the full combinations table.

Trade-offs

Pros

More space-efficient than the pure recursive approach. Can achieve O(N) space if combinations are computed using factorials.
Cleaner separation of concerns: first building the structure, then performing calculations on it.
Generally faster in practice due to avoiding list manipulation overhead.

Cons

The worst-case time complexity is still O(N^2) due to BST construction for skewed inputs (like a sorted array).

Solutions

Solution

1class Solution {2private3  int[][] c;4private5  final int mod = (int)1 e9 + 7;6public7  int numOfWays(int[] nums) {8    int n = nums.length;9    c = new int[n][n];10    c[0][0] = 1;11    for (int i = 1; i < n; ++i) {12      c[i][0] = 1;13      for (int j = 1; j <= i; ++j) {14        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;15      }16    }17    List<Integer> list = new ArrayList<>();18    for (int x : nums) {19      list.add(x);20    }21    return (dfs(list) - 1 + mod) % mod;22  }23private24  int dfs(List<Integer> nums) {25    if (nums.size() < 2) {26      return 1;27    }28    List<Integer> left = new ArrayList<>();29    List<Integer> right = new ArrayList<>();30    for (int x : nums) {31      if (x < nums.get(0)) {32        left.add(x);33      } else if (x > nums.get(0)) {34        right.add(x);35      }36    }37    int m = left.size(), n = right.size();38    int a = dfs(left), b = dfs(right);39    return (int)((long)a * b % mod * c[m + n][n] % mod);40  }41}

1class Solution {2public:3  int numOfWays(vector<int> &nums) {4    int n = nums.size();5    const int mod = 1e9 + 7;6    int c[n][n];7    memset(c, 0, sizeof(c));8    c[0][0] = 1;9    for (int i = 1; i < n; ++i) {10      c[i][0] = 1;11      for (int j = 1; j <= i; ++j) {12        c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;13      }14    }15    function<int(vector<int>)> dfs = [&](vector<int> nums) -> int {16      if (nums.size() < 2) {17        return 1;18      }19      vector<int> left, right;20      for (int &x : nums) {21        if (x < nums[0]) {22          left.push_back(x);23        } else if (x > nums[0]) {24          right.push_back(x);25        }26      }27      int m = left.size(), n = right.size();28      int a = dfs(left), b = dfs(right);29      return c[m + n][m] * 1ll * a % mod * b % mod;30    };31    return (dfs(nums) - 1 + mod) % mod;32  }33};

1class Solution:2    def numOfWays(self, nums: List[int]) -> int: 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 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 return (dfs(nums) - 1 + mod) % mod

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem