← Back to DSA Animator
Insert Interval LC #57 Medium Intervals · Three-Phase
Problem

You are given an array of non-overlapping intervals intervals sorted by start. Insert newInterval in the correct position (merge if necessary).

Example
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: [4,8] overlaps [3,5], [6,7], [8,10] → merge to [3,10].
Constraints: 0 ≤ intervals.length ≤ 10⁴  |  intervals sorted by starti
Try Examples
Approach
Three-Phase Linear Scan
Phase 1: Add intervals with end < new.start. Phase 2: Merge overlapping (start ≤ new.end). Phase 3: Add rest.
Interval Timeline
Load an example to begin.
Variables
Phase
—
i
—
newInterval
—
Action
—
Step Logic
Press ▶ Play or Next Step to begin.
✓
Ready
0 / 0
Select an example and press Play.
Algorithm
1
Phase 1: Add intervals with end < new.start
2
Phase 2: Merge overlaps: new = [min(new[0],iv[0]), max(new[1],iv[1])]
3
Phase 3: Add remaining intervals
Time
O(n)
Space
O(n)
Why Three Phases

Intervals are sorted. Phase 1 adds those entirely before the new interval. Phase 2 merges all overlapping intervals in one pass. Phase 3 adds those entirely after.