Insert Interval

Insert Interval is Merge Intervals with a gift: the list is already sorted and has no overlaps. The gift is a trap if you ignore it, because the obvious answer re-sorts and pays O(n log n) for work that takes O(n).

The problem

You are given a list of intervals that are sorted by start and do not overlap each other, and one new interval. Insert the new interval so that the list stays sorted and non-overlapping, merging wherever the new interval overlaps or touches existing ones. Return the new list.

• intervals = [[1, 2], [4, 6], [7, 9], [12, 14]], new = [5, 8] → [[1, 2], [4, 9], [12, 14]]. [5, 8] overlaps both [4, 6] and [7, 9], and the three become [4, 9].
• intervals = [[1, 2], [5, 6]], new = [3, 4] → [[1, 2], [3, 4], [5, 6]]. It falls in a gap and touches nothing.

Constraints: 0 ≤ n ≤ 10⁴, the list is sorted by start and non-overlapping, start ≤ end everywhere.

Clarifying questions

• Do touching intervals merge? Yes: inserting [2, 3] into [[1, 2], [3, 4]] gives [[1, 4]].
• Can the list be empty? Yes; then the answer is just [new].
• Return a new list or change the input? Return a new list.

Approach 1: append and merge

Add the new interval to the end and run the Merge Intervals solution.

def insert_by_merging(intervals: list[list[int]], new: list[int]) -> list[list[int]]:    """Append the new interval and run the full merge."""    return merge(intervals + [new])

It is correct, and a fine first thing to say. But merge sorts, which is O(n log n), and the input was already sorted. Only one interval is out of place. At n = 10⁴ it runs fast either way; the interviewer is checking whether you notice that the sort is wasted work.

The key insight

Because the list is sorted and non-overlapping, its intervals relate to the new one in three contiguous groups:

1. Intervals that end before the new one starts. They are untouched. In a sorted, disjoint list the ends increase from left to right, so all of these sit at the front.
2. Intervals that start after the new one ends. They are untouched too. The starts also increase, so all of these sit at the back.
3. Everything in between neither ends before the new interval nor starts after it — so it overlaps the new one and gets absorbed into it.

In list order that is: before, overlapping, after.

So one pass with three short while loops does the whole job, each interval visited once. In phase 2 the new interval can grow in both directions — an absorbed interval may start before it — so it needs a min on the start as well as a max on the end. That differs from Merge Intervals, where the start never moves.

Approach 2: three phases in one pass

1def insert(intervals: list[list[int]], new: list[int]) -> list[list[int]]:2    """Three phases over a sorted, non-overlapping list: before, overlapping, after."""3    result: list[list[int]] = []4    i, n = 0, len(intervals)5    start, end = new6    while i < n and intervals[i][1] < start:     # 1. ends before new starts7        result.append(intervals[i])8        i += 19    while i < n and intervals[i][0] <= end:      # 2. overlaps: absorb it10        start = min(start, intervals[i][0])11        end = max(end, intervals[i][1])12        i += 113    result.append([start, end])14    while i < n:                                 # 3. starts after new ends15        result.append(intervals[i])16        i += 117    return result

Dry run on [[1, 2], [4, 6], [7, 9], [12, 14]] with new = [5, 8].

Result [[1, 2], [4, 9], [12, 14]]. The start moved left from 5 to 4 in phase 2 — the min at work.

Complexity. Each interval is looked at by exactly one phase, once: O(n) time. Space O(n) for the result.

Phase 1 uses a strict <: an interval ending exactly where the new one starts touches it, so it belongs to phase 2 and merges. Phase 2 uses <= for the same reason at the other end.

Notice what phase 2 does not check. It never tests whether the interval ends after start, because phase 1 already guaranteed that: any interval that ended before start was copied. And as phase 2 absorbs intervals, end only grows, so its test intervals[i][0] <= end stays the only thing that decides when the overlapping run is over. Each loop has one condition, and that is why this solution is easy to get right under pressure.

Edge cases

• Empty list: phases 1 and 3 do nothing; the result is [new].
• New interval before everything, [[5, 6]] + [1, 2]: phase 1 copies nothing, phase 2 absorbs nothing, [1, 2] is appended, phase 3 copies [5, 6].
• New interval after everything: phase 1 copies all, then new is appended.
• New interval inside an existing one, [[1, 5]] + [2, 3]: phase 2 absorbs [1, 5], and the min/max keep it [1, 5].
• New interval covering everything, [[3, 5], [7, 9]] + [1, 10]: phase 2 absorbs both; the result is [[1, 10]].
• Touching on both sides, [[1, 2], [3, 4]] + [2, 3]: both merge into [[1, 4]].

Follow-ups

• "Can you find the phase boundaries faster?" Yes: binary search for the first interval with end >= new.start and the first with start > new.end, O(log n). The output still has to be built, so the total stays O(n) unless you may splice the list in place.
• "Insert many intervals, one after another." Keep the intervals in a balanced tree or sorted container keyed by start, so each insert touches only its neighbours.
• "Remove an interval instead" (Remove Interval). Same three phases; in phase 2, keep the parts of each interval that stick out on the left or right of the removed range.