Insert Interval

Explanation & Solution

Description

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and end of the i-th interval, and intervals is sorted in ascending order by start_i.

You are also given an interval newInterval = [start, end] that represents the interval to be inserted.

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Input:intervals = [[1,3],[6,9]], newInterval = [2,5]

Output: [[1,5],[6,9]]

Explanation: The new interval [2,5] overlaps with [1,3]. Merging them gives [1,5]. The interval [6,9] does not overlap, so the result is [[1,5],[6,9]].

Constraints

0 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start_i <= end_i <= 10⁵
intervals is sorted by start_i in ascending order
newInterval.length == 2
0 <= start <= end <= 10⁵

Approach

Intervals pattern

1. Initialize Result and Pointer

Create an empty result array to build the answer
Use pointer i to scan through the existing intervals from left to right

2. Phase 1 — Add Non-Overlapping Intervals Before

While intervals[i][1] < newInterval[0] (current interval ends before the new one starts), the intervals don't overlap
Push these intervals directly into result — they remain unchanged
Advance i after each addition

3. Phase 2 — Merge Overlapping Intervals

While intervals[i][0] <= newInterval[1] (current interval starts before the new one ends), there is an overlap
Merge by expanding newInterval:
start = Math.min(newInterval[0], intervals[i][0])
end = Math.max(newInterval[1], intervals[i][1])
This absorbs each overlapping interval into newInterval
Advance i after each merge

4. Push the Merged Interval

After all overlapping intervals have been merged, push newInterval into result
This single interval replaces all the intervals it overlapped with

5. Phase 3 — Add Remaining Intervals After

Any intervals still unprocessed start after the merged interval ends
Push them all directly into result — they remain unchanged

6. Return the Result

The result array now contains all intervals in sorted order with no overlaps
Time complexity is O(n) because each interval is visited exactly once
Space complexity is O(n) for the output array

Key Insight

The three-phase approach works because the input intervals are already sorted and non-overlapping. This lets us cleanly partition them into three groups: intervals entirely before the new one, intervals that overlap (and must be merged), and intervals entirely after. The overlap condition intervals[i][0] <= newInterval[1] is the critical check — once it fails, no further intervals can overlap because they are sorted by start time.

Visualization

Input:

Interval Timeline[[1,3], [6,9]]

—

Press play to start visualization

CurrentCompareOverlapMerged

4 steps

Solution Code

Merge Intervals

Interval List Intersections