Skip to content

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

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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;
  }
}