Number of Ways to Reorder Array to Get Same BST

This page explains Java solution to problem Number of Ways to Reorder Array to Get Same BST using Dynamic Programming algorithm.

Problem Statement

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^9 + 7.

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.

Input: [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]

Input: nums = [1,2,3]
Output: 0

Input: nums = [9,4,2,1,3,6,5,7,8,14,11,10,12,13,16,15,17,18]
Output: 216212978
Explanation: The number of ways to reorder nums to get the same BST is 3216212999. Taking this number modulo 10^⁹ + 7 gives 216212978.

Solution

package com.vc.hard;

import java.util.*;

class NumberOfWaysToReorderArrayToGetSameBst {
    private long[][] pascal;
    private int MOD = (int)1e9 + 7;

    public int numOfWays(int[] nums) {
        int n = nums.length;
        generatePascal(n + 1);

        List<Integer> numbers = new ArrayList<>();
        for(int i = 0; i < nums.length; i++) numbers.add(nums[i]);

        //-1 because one permutation is already given as an input
        return (int)helper(numbers) - 1;
    }

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

        int root = nums.get(0);
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();

        for(int i = 1; i < nums.size(); i++) {
            int num = nums.get(i);
            if(num > root) right.add(num);
            else left.add(num);
        }

        /**
             How many different ways we can arrange left.size() elements in left.size() + right.size() elements

             Let's say we have [3, 4, 5, 1, 2] as original array with root value is 3

             [1, 2] left sub-tree, left.size() = 2
             [4, 5] right sub-tree, right.size() = 2

             In all of below permutations, we keep relative position in left & right subtree,
             But we can absolute position
             [1, 2, 4, 5]
             [1, 4, 2, 5]
             [1, 4, 5, 2]
             [4, 1, 2, 5]
             [4, 1, 5, 2]
             [4, 5, 1, 2]
         */
        return pascal[left.size() + right.size()][left.size()] % MOD *
                helper(left) % MOD *
                helper(right) % MOD;
    }

    private void generatePascal(int n) {
        pascal = new long[n][n];
        for(int row = 0; row < n; row++) pascal[row][0] = pascal[row][row] = 1;

        for(int row = 2; row < n; row++) {
            for(int col = 1; col < row; col++) {
                pascal[row][col] = (pascal[row - 1][col] + pascal[row - 1][col - 1]) % MOD;
            }
        }
    }
}

Time Complexity

O(N²) Where
N is number of elements in an input array nums

Space Complexity

O(N * N) Where
N is number of elements in an input array nums