Number of Ways to Reorder Array to Get Same BST

Hard

Google

2 views

Topics:

TreesRecursionDynamic Programming

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.

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]

Constraints:

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

Number of Ways to Reorder Array to Get Same BST

Hard

Google

2 views

Topics:

TreesRecursionDynamic Programming

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.

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]

Constraints:

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array `nums`? I'm thinking about potential stack overflow issues with recursion.
Can the elements in the input array `nums` contain duplicate values? If so, how should they be handled when constructing the BST?
Can the input array `nums` be empty or null? If so, what should the function return in these cases?
Are the elements in the input array `nums` guaranteed to be distinct integers, or can there be non-integer types?
Could you provide an example of an input array and the expected output, especially in cases where the answer might be 0 or 1?

Brute Force Solution

Approach

The goal is to count arrangements of numbers that build the same binary search tree (BST). The brute force method involves generating every possible arrangement of the numbers, then for each arrangement, building a BST and comparing its structure to the structure of the BST we want.

Here's how the algorithm would work step-by-step:

First, list every single possible way to order the numbers.
For each of these orderings, construct a binary search tree using that ordering.
Compare the structure of this tree with the structure of the original tree we're aiming for.
If the structures are identical, then that ordering counts as a valid arrangement.
Keep track of the number of arrangements that produce identical tree structures.
Once you've checked all the possible orderings, the number you've kept track of will be your answer.

Code Implementation

from itertools import permutations

def number_of_ways_to_reorder_array_to_get_same_bst_brute_force(numbers):

    def construct_bst(array):
        if not array:
            return None

        root_node = array[0]
        left_subtree = [number for number in array[1:] if number < root_node]
        right_subtree = [number for number in array[1:] if number > root_node]

        return (root_node, construct_bst(left_subtree), construct_bst(right_subtree))

    original_bst = construct_bst(numbers)
    count_of_identical_bsts = 0

    # Iterate through each possible permutation of the input numbers
    for permutation in permutations(numbers):
        
        current_bst = construct_bst(list(permutation))

        #Compare the generated BST with the original BST.
        if current_bst == original_bst:
            count_of_identical_bsts += 1

    # Subtract 1 to exclude the original array itself
    return count_of_identical_bsts - 1

Big(O) Analysis

Time Complexity

O(n! * n^2) – The solution first generates all possible permutations of the input array of size n. Generating all permutations takes O(n!) time. For each permutation, it constructs a binary search tree, which takes O(n) time since inserting each element into the BST takes O(height) time and in the worst case height can be n. Then, comparing the structure of the constructed BST with the original BST takes O(n) time as we need to traverse both trees. Therefore the overall time complexity is O(n! * (n + n)) which simplifies to O(n! * n^2).

Space Complexity

O(N) – The brute force method generates all possible orderings of the N numbers. For each ordering, a binary search tree is constructed. The construction of each BST may require auxiliary space proportional to the number of nodes, up to N in the worst case, to store the tree structure (nodes and their connections). The maximum space used across all tree constructions would be O(N). Therefore, the space complexity is O(N).

Optimal Solution

Approach

The key insight is that the first number in the array will always be the root of the BST. Once we know the root, we can determine which numbers will be in the left and right subtrees. Then we can recursively solve the problem for each subtree and combine the results.

Here's how the algorithm would work step-by-step:

Recognize that the original array dictates the root of the BST.
Separate the remaining numbers into two groups: those smaller than the root (left subtree) and those larger than the root (right subtree).
Figure out how many ways you can arrange these two groups amongst themselves, independently.
Calculate how many ways you can merge those two arranged groups into a single sequence, where the order of each group is maintained. This involves figuring out the number of combinations for interleaving the two groups.
Multiply the number of ways to arrange the left subtree, the number of ways to arrange the right subtree, and the number of ways to merge the two groups.
Recursively repeat this process for the left subtree and the right subtree.
Handle the base case where a subtree contains zero or one number. In this case, there is only one way to arrange it.
Finally, subtract 1 from the result to account for the original array's arrangement which we are not counting.

Code Implementation

def number_of_ways_to_reorder_array_to_get_same_bst(numbers):

    def combinations(total_items, items_to_choose, modulo):
        if items_to_choose < 0 or items_to_choose > total_items:
            return 0
        if items_to_choose == 0 or items_to_choose == total_items:
            return 1
        if items_to_choose > total_items // 2:
            items_to_choose = total_items - items_to_choose
        
        result = 1
        for i in range(items_to_choose):
            result = (result * (total_items - i)) % modulo
            result = (result * pow(i + 1, modulo - 2, modulo)) % modulo
        return result

    def number_of_ways(nums, modulo):
        number_of_elements = len(nums)
        if number_of_elements <= 1:
            return 1

        root_value = nums[0]
        left_subtree_elements = [num for num in nums[1:] if num < root_value]
        right_subtree_elements = [num for num in nums[1:] if num > root_value]

        # Recursively calculate number of ways for subtrees
        left_ways = number_of_ways(left_subtree_elements, modulo)
        right_ways = number_of_ways(right_subtree_elements, modulo)

        # Calculate combinations to merge subtrees
        number_of_left_elements = len(left_subtree_elements)
        merge_ways = combinations(number_of_left_elements + len(right_subtree_elements), number_of_left_elements, modulo)

        # Multiply the results
        return (left_ways * right_ways * merge_ways) % modulo

    modulo = 10**9 + 7
    # Subtract 1 to exclude the original array
    return (number_of_ways(numbers, modulo) - 1) % modulo

Big(O) Analysis

Time Complexity

O(n²) – The initial function call processes the entire input array of size n. Within each call, we iterate through all n elements to partition them into left and right subtrees. Additionally, calculating combinations (n choose k) using a naive approach involves another loop up to n. Therefore, the time complexity can be approximated as n * n for partitioning and combinations within each recursive call. The recursion tree has a depth of at most n, leading to an overall time complexity of O(n²).

Space Complexity

O(N^2) – The dominant space complexity arises from the combinations calculation. The combination formula (n choose k) is often precomputed and stored in a table to avoid redundant calculations. In the worst case, we may need to calculate combinations for all possible pairs of numbers up to N, leading to a table of size N x N. The recursive calls contribute a space complexity of O(N) in the worst case due to the call stack. However, the space needed for combinations dominates, resulting in an overall space complexity of O(N^2).

Edge Cases

Case	How to Handle
Null or empty input array	Return 1, as an empty tree or null input is considered a valid BST with one possible arrangement.
Array with a single element	Return 1, as a single-node tree has only one possible arrangement.
Array with two elements	Return 1, as there is only one possible arrangement for a BST with two nodes (root and one child).
Array with all elements equal	Return 1, as all permutations will result in the same BST structure.
Maximum input size exceeding recursion limit	Employ memoization for combinations to avoid recomputation and potentially exceeding the recursion depth limit.
Integer overflow in binomial coefficient calculation (combinations)	Use modular arithmetic (modulo 10^9 + 7) during the computation of binomial coefficients to prevent integer overflow.
Highly skewed input distribution (e.g., nearly sorted)	The algorithm's performance is not significantly affected by skewed input distributions as it depends on the BST structure rather than the initial ordering.
Zero as an element in the input array	Zero is treated as a regular number and does not require special handling in the BST construction or reordering process.