Number of Ways to Reorder Array to Get Same BST — LeetCode 1569 Python Solution
HardTreeUnion FindBinary Search TreeMemoizationArrayMathDivide and ConquerDynamic ProgrammingBinary TreeCombinatorics
- Problem
- #1569
- Pattern
- Union-Find
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
Python
class Solution:
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) % modComplexity
| Measure | Complexity |
|---|---|
| Time | O(n^2) |
| Space | O(n^2) auxiliary |
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1569. Number of Ways to Reorder Array to Get Same BST is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
LeetCode 96Unique Binary Search TreesMediumLeetCode 95Unique Binary Search Trees IIMediumLeetCode 894All Possible Full Binary TreesMediumLeetCode 1373Maximum Sum BST in Binary TreeHardLeetCode 1467Probability of a Two Boxes Having The Same Number of Distinct BallsHardLeetCode 1643Kth Smallest InstructionsHard
Frequently asked questions
- How hard is LeetCode 1569. Number of Ways to Reorder Array to Get Same BST?
- LeetCode 1569. Number of Ways to Reorder Array to Get Same BST is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1569. Number of Ways to Reorder Array to Get Same BST?
- The Python solution on this page runs in O(n^2).
- What is the space complexity of LeetCode 1569. Number of Ways to Reorder Array to Get Same BST?
- The Python solution on this page uses O(n^2) auxiliary space.
- What topics does LeetCode 1569. Number of Ways to Reorder Array to Get Same BST cover?
- LeetCode 1569. Number of Ways to Reorder Array to Get Same BST is tagged Tree, Union Find, Binary Search Tree, Memoization, Array, Math, Divide and Conquer, Dynamic Programming, Binary Tree and Combinatorics on LeetCode.