Given a sorted list of non-overlapping intervals and a new interval, insert and merge if necessary.
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] → Output: [[1,2],[3,10],[12,16]]
TimeO(n)single pass
SpaceO(n)result list
i: —new: —Result: —
Before
Overlap / Merging
Merged
After
newInterval
—
Result
—
Ready
Press Play. Three phases: add intervals before overlap, merge overlapping, add intervals after.
TimeO(n)linear recurse
SpaceO(n)result + call stack
Recursive: base cases for empty, before-all, after-all. If current interval ends before new, prepend and recurse. Otherwise merge and recurse on rest.
✎ Whiteboard
3
⌨ Type It
Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.
═══ INSERT INTERVAL — 3 PHASES ═══
PATTERN ▸ Before / Merge / After O(n) · O(n)
① BEFORE: add all intervals ending before new
while intervals[i][1] < newInterval[0]: append, i++