0

What is the time complexity of the addNum operation in the optimal balanced tree approach for maintaining disjoint intervals, assuming there are n intervals stored?

medium🪤 Complexity Trap Q13 of Q15

Intervals - Data Stream as Disjoint Intervals

What is the time complexity of the addNum operation in the optimal balanced tree approach for maintaining disjoint intervals, assuming there are n intervals stored?

AO(n) because intervals need to be scanned linearly for merging

BO(log n) due to binary search and limited merging operations

CO(n log n) because each insertion requires sorting intervals

DO(1) since insertion is always at the end or start

Step-by-Step Solution

Solution:

Step 1: Identify main operations in addNum
addNum uses binary search (bisect_left) to find insertion index in O(log n).
Step 2: Analyze merging cost
Merging involves at most constant number of interval merges (left, right, or both), so O(1) extra work.
Final Answer:
Option B -> Option B
Quick Check:
Binary search dominates, merges are constant time [OK]

Quick Trick: Binary search + constant merges -> O(log n) [OK]

Common Mistakes:

MISTAKES

Assuming linear scan for merging
Confusing sorting cost per insertion
Ignoring constant merge steps

Trap Explanation:

PITFALL

Candidates often think merging requires scanning all intervals, inflating complexity to O(n).

Interviewer Note:

CONTEXT

Checks understanding of balanced tree operations and merge cost in interval maintenance.

Master "Data Stream as Disjoint Intervals" in Intervals

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions

More Intervals Quizzes