1417. Nested Inside Counts
A genome browser shows n annotated regions. Region i is the closed range from starts[i] to starts[i] + lengths[i]; its right end can exceed 32-bit range, so use 64-bit arithmetic.
For every region i, return how many other regions j != i lie entirely inside it, meaning starts[i] <= starts[j] and end[j] <= end[i]. Two identical regions count as inside each other. Return the counts as an array in input order.
A good plan is to process regions by decreasing start in groups of equal start, keep a Fenwick tree over the compressed right ends, and query how many stored ends are at most the current end. Target O(n log n) time and O(n) space.
Example 1
- Input:
- starts = [1,2,5,1], lengths = [10,2,1,3]
- Output:
- [3,0,0,1]
- Explanation:
Region 0 is [1,11) and contains region 1 = [2,4), region 2 = [5,6) and region 3 = [1,4); region 3 contains region 1; the others contain nothing.
Example 2
- Input:
- starts = [4,4], lengths = [3,3]
- Output:
- [1,1]
- Explanation:
Both regions are [4,7), so each contains the other.
Example 3
- Input:
- starts = [0], lengths = [0]
- Output:
- [0]
- Explanation:
A single region has no other region to contain.
Constraints
- 1 ≤ n ≤ 105, where n is the length of
starts - starts.length == lengths.length
- 0 ≤ starts[i], lengths[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 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)