DSA AnimatorDSA animations
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.

How to solve Insert Interval

LeetCode 57 · Medium · Intervals · Pattern: Three-Phase Scan

Why the obvious approach is slow

You could append the new interval, sort everything, and run merge intervals. But the list is already sorted, so one linear scan is enough.

The key idea

First, copy every interval that ends before the new one starts. Then, while intervals start before the new one ends, merge them into it by widening its start and end. Finally, add the merged interval and copy everything after it.

Remember

Before, overlapping, after. Three simple loops, and no sorting.

Run the animation above on your own input, or watch the 1:24 video explanation of Insert Interval with a dry run and Java code.

More Intervals problems