1653. Same Shape Orders
A records clerk files the unique ticket numbers 1 to n into an initially empty binary search tree. The first ticket becomes the root; every later ticket walks down from the root, going left at a smaller key and right at a larger key, until it reaches a free slot and settles there.
You are given nums, the order in which the tickets arrive, a permutation of 1 to n. Count how many different arrival orders (permutations of 1 to n) would build a tree with exactly the same shape and key placement as the one built from nums. The order nums itself counts, so the answer is always at least 1. Return the count modulo 1000000007.
Aim for O(n) time and O(n) space; the tree can be a chain of n levels, so avoid deep recursion.
Example 1
- Input:
- nums = [2,1,3]
- Output:
- 2
- Explanation:
Both orderings 2,1,3 and 2,3,1 build the same tree with root 2, so the answer is 2.
Example 2
- Input:
- nums = [1,2,3]
- Output:
- 1
- Explanation:
Only the ordering 1,2,3 builds this right-leaning chain, so the answer is 1.
Example 3
- Input:
- nums = [3,4,5,1,2]
- Output:
- 6
- Explanation:
Root 3 has a left part {1,2} and a right part {4,5}; interleavings of the two sides give 6 orderings.
Constraints
1 ≤ n ≤ 105
nums is a permutation of 1..n
answer modulo 109 + 7
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)