Insert Interval Solution

Problem

You have a list of non-overlapping intervals sorted by their start times. Insert a new interval anywhere it fits — merging with existing intervals wherever they overlap — and return the updated list.

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: The new interval [2,5] overlaps with [1,3], so they merge into [1,5].

A second example to show multi-merge behavior:

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], and [8,10], swallowing all three into [3,10].

Intuition

The list is already sorted, which lets us handle this in three distinct phases — intervals that end before the new one starts pass through unchanged, intervals that overlap get absorbed into the new one (expanding it as needed), and everything after passes through unchanged. The key boundary condition is that two intervals overlap whenever one starts at or before the other ends (a[0] <= b[1]), not strictly before — [1,2] and [2,3] must merge into [1,3].

Approaches — how many to write

Two meaningful approaches exist: a sort-based approach (works even on unsorted input) and a linear scan that exploits the sorted guarantee.

Approach 1 — Sort and Merge

Append the new interval, sort everything by start time, then do a single left-to-right merge pass. This reduces the problem to the standard Merge Intervals pattern and requires no special case handling.

Append newInterval to the list.
Sort all intervals by start value.
Initialize a result list with the first interval.
For each subsequent interval, if it overlaps with the last result interval, extend the last interval's end; otherwise append it.
Return the result list.

1def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
2    all_intervals = intervals + [newInterval]
3    all_intervals.sort(key=lambda x: x[0])
4
5    result = [all_intervals[0]]
6    for start, end in all_intervals[1:]:
7        if start <= result[-1][1]:  # overlaps with last merged interval
8            result[-1][1] = max(result[-1][1], end)
9        else:
10            result.append([start, end])
11    return result

Time: O(n log n) — dominated by the sort over n + 1 intervals.
Space: O(n) — the result list holds at most n + 1 intervals.

Approach 2 — Linear Three-Phase Scan

Since the input is already sorted, skip the sort entirely. Walk through in three phases: copy intervals that end before the new one starts, merge all overlapping intervals into the new one, then copy the rest. Each interval is visited exactly once.

Copy every interval whose end is strictly less than newInterval's start — these cannot possibly overlap.
For every remaining interval whose start is at or before newInterval's current end, expand newInterval to cover the union.
Append the (now fully merged) newInterval to the result.
Copy all remaining intervals after the overlap zone unchanged.

1def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
2    result = []
3    i = 0
4    n = len(intervals)
5
6    # Phase 1: intervals that end before newInterval starts — no overlap possible
7    while i < n and intervals[i][1] < newInterval[0]:
8        result.append(intervals[i])
9        i += 1
10
11    # Phase 2: absorb all overlapping intervals into newInterval
12    while i < n and intervals[i][0] <= newInterval[1]:
13        newInterval[0] = min(newInterval[0], intervals[i][0])
14        newInterval[1] = max(newInterval[1], intervals[i][1])
15        i += 1
16    result.append(newInterval)
17
18    # Phase 3: intervals that start after newInterval ends — no overlap possible
19    while i < n:
20        result.append(intervals[i])
21        i += 1
22
23    return result

Time: O(n) — each interval is visited at most once across all three phases.
Space: O(n) — the output list contains at most n + 1 intervals.

Complexity Summary

Approach	Time	Space	When to use
Sort and Merge	O(n log n)	O(n)	When input may not be sorted, or when reusing a merge-intervals helper
Linear Three-Phase Scan	O(n)	O(n)	When the input is guaranteed sorted (as stated in this problem)

Common Mistakes

Using strict < instead of <= for the overlap check — intervals [1,2] and [2,3] share the endpoint 2 and must merge into [1,3]; using < leaves them separate.
Forgetting to append newInterval after Phase 2 — it's easy to merge everything into newInterval and then skip adding it to the result, especially when the new interval ends up covering the entire list.
Extending newInterval only in one direction — when absorbing an overlapping interval, you must update both the start (min) and the end (max), not just the end.
Off-by-one in Phase 1's boundary — the condition is intervals[i][1] < newInterval[0] (strictly less), not <=. If an existing interval ends exactly where the new one starts, they touch and should merge.
Mutating the original intervals array in Approach 1 without a copy — calling intervals.push_back(newInterval) modifies the caller's data in C++; this may be acceptable in an interview but violates the principle of not modifying inputs unexpectedly.

Insert Interval — Solution