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

In this guide, you will get 1569. Number of Ways to Reorder Array to Get Same BST LeetCode Solution with the best time and space complexity. The solution to Number of Ways to Reorder Array to Get Same BST problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Number of Ways to Reorder Array to Get Same BST solution in C++
Number of Ways to Reorder Array to Get Same BST solution in Java
Number of Ways to Reorder Array to Get Same BST solution in Python
Additional Resources

1569. Number of Ways to Reorder Array to Get Same BST LeetCode Solution image

Problem Statement of Number of Ways to Reorder Array to Get Same BST

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 109 + 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.

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n^2)

1569. Number of Ways to Reorder Array to Get Same BST LeetCode Solution in C++

class Solution {
 public:
  int numOfWays(vector<int>& nums) {
    comb = generate(nums.size() + 1);
    return ways(nums) - 1;
  }

 private:
  static constexpr int kMod = 1'000'000'007;
  // comb[n][k] := C(n, k)
  vector<vector<int>> comb;

  int ways(const vector<int>& nums) {
    if (nums.size() <= 2)
      return 1;

    vector<int> left;
    vector<int> 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]);

    long ans = comb[nums.size() - 1][left.size()];
    ans = (ans * ways(left)) % kMod;
    ans = (ans * ways(right)) % kMod;
    return ans;
  }

  // Same as 118. Pascal's Triangle
  vector<vector<int>> generate(int numRows) {
    vector<vector<int>> comb;

    for (int i = 0; i < numRows; ++i)
      comb.push_back(vector<int>(i + 1, 1));

    for (int i = 2; i < numRows; ++i)
      for (int j = 1; j < comb[i].size() - 1; ++j)
        comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % kMod;

    return comb;
  }
};
/* code provided by PROGIEZ */

1569. Number of Ways to Reorder Array to Get Same BST LeetCode Solution in Java

class Solution {
  public int numOfWays(int[] nums) {
    comb = generate(nums.length + 1);
    return ways(Arrays.stream(nums).boxed().collect(Collectors.toList())) - 1;
  }

  private static final int kMod = 1_000_000_007;
  // comb[n][k] := C(n, k)
  private List<List<Integer>> comb;

  private int ways(List<Integer> nums) {
    if (nums.size() <= 2)
      return 1;

    List<Integer> left = new ArrayList<>();
    List<Integer> right = new ArrayList<>();

    for (int i = 1; i < nums.size(); ++i)
      if (nums.get(i) < nums.get(0))
        left.add(nums.get(i));
      else
        right.add(nums.get(i));

    long ans = comb.get(nums.size() - 1).get(left.size());
    ans = (ans * ways(left)) % kMod;
    ans = (ans * ways(right)) % kMod;
    return (int) ans;
  }

  // Same as 118. Pascal's Triangle
  public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> comb = new ArrayList<>();

    for (int i = 0; i < numRows; ++i) {
      Integer[] temp = new Integer[i + 1];
      Arrays.fill(temp, 1);
      comb.add(Arrays.asList(temp));
    }

    for (int i = 2; i < numRows; ++i)
      for (int j = 1; j < comb.get(i).size() - 1; ++j)
        comb.get(i).set(j, (comb.get(i - 1).get(j - 1) + comb.get(i - 1).get(j)) % kMod);

    return comb;
  }
}
// code provided by PROGIEZ