1652. Insertion Depth Ledger
A scoreboard keeps its entries in a binary search tree, starting empty. Scores arrive one at a time from the left of the array nums. The first score becomes the root; each later score starts at the root and moves to the left child if it is strictly smaller than the node it meets, otherwise (equal or larger) to the right child, until it lands in a free spot.
Return an array of the same length where element i is the depth of the node created for nums[i] at the moment it is inserted; the root has depth 1. Because later insertions never move existing nodes, this is also its final depth.
Do not simulate the insertions: sorted or all-equal input makes the tree n levels deep. Aim for O(n log n) time and O(n) space.
Example 1
- Input:
- nums = [5,3,8,4]
- Output:
- [1,2,2,3]
- Explanation:
Value 5 is the root at depth 1, 3 and 8 sit below it at depth 2, and 4 goes left of 5 then right of 3 at depth 3.
Example 2
- Input:
- nums = [2,2,2]
- Output:
- [1,2,3]
- Explanation:
Equal values go to the right subtree, so the three 2s form a chain of depths 1, 2 and 3.
Constraints
1 ≤ n ≤ 105
-109 ≤ nums[i] ≤ 109
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 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)