Insert a new interval into a sorted, non-overlapping interval list

TL;DR: Single O(n) pass in three phases: copy intervals strictly before the new one, absorb every interval that overlaps it (widening start/end), then copy the rest. Two intervals overlap iff a <= d and c <= b.

How to approach it This is usually asked as a follow-up to merge-intervals, and the lazy answer ("append, then re-run merge") works but wastes the sorted invariant. State both options and their costs: re-merge is O(n log n); exploiting sortedness is O(n) in a single pass. Then name the structure out loud: the result has three phases: intervals entirely before the new one, intervals that overlap it (absorb them), intervals entirely after.

The overlap condition is worth writing on the whiteboard before coding: intervals [a, b] and [c, d] overlap iff a <= d and c <= b. Deriving it calmly is a known differentiator on this question.

A strong answer

def insert_interval(intervals: list[list[int]],
                    new: list[int]) -> list[list[int]]:
    start, end = new
    result, i, n = [], 0, len(intervals)

    while i < n and intervals[i][1] < start:      # phase 1: strictly before
        result.append(intervals[i]); i += 1

    while i < n and intervals[i][0] <= end:       # phase 2: overlapping, absorb
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    result.append([start, end])

    result.extend(intervals[i:])                  # phase 3: strictly after
    return result

Each loop guard is one half of the overlap condition. Say that, because it shows the code follows from the math rather than trial and error. O(n) time, one pass, no sort.

The absorbing-three case from the tests below, traced by running the code, shows the phase the editor note warns about:

Step 4 is the whole question in one row: the new interval had already grown to [3,8], and [8,10] touches it at exactly 8, so the <= guard pulls it in and the span becomes [3,10]. Write < there instead and the output is [[1,2],[3,8],[8,10],[12,16]], two intervals sharing a boundary point in a list whose invariant says non-overlapping, and every downstream consumer of that invariant is now subtly broken. Also worth noticing in the trace: the span grows while absorbing (step 4 widens the end from 8 to 10 mid-loop), which is the "extends past several existing ones at once" behavior that the append-and-re-merge shortcut hides from you and the three-phase version makes explicit.

Tests, unprompted, hitting every phase boundary:

assert insert_interval([[1, 3], [6, 9]], [2, 5]) == [[1, 5], [6, 9]]
assert insert_interval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) \
       == [[1, 2], [3, 10], [12, 16]]            # absorbs three intervals
assert insert_interval([], [5, 7]) == [[5, 7]]    # empty list
assert insert_interval([[1, 5]], [6, 8]) == [[1, 5], [6, 8]]   # after all
assert insert_interval([[3, 5]], [1, 2]) == [[1, 2], [3, 5]]   # before all
assert insert_interval([[1, 5]], [2, 3]) == [[1, 5]]           # fully contained

What interviewers probe next (1) Many inserts over time? A list makes each insert O(n); discuss an interval tree or a balanced BST keyed by start for O(log n). Naming the structure and its tradeoff (complexity vs. how many inserts you actually expect) is enough. (2) Delete/subtract an interval? Same three-phase shape, but phase 2 may split an interval into two; sketch it. (3) Booking system semantics: Palantir flavors this as "can this meeting be scheduled?", which is just phase 2 returning a boolean.

Common mistakes Off-by-one on the guards: intervals[i][1] < start vs <= changes whether touching intervals merge; tie it back to the boundary semantics you clarified. Forgetting to append the merged interval when the input list is empty or when the new interval lands after everything (the append outside both loops handles both; point that out). Re-deriving overlap logic by patching failing cases live, which reads as guessing. And jumping straight to the interval-tree answer for a single insert: premature generality is a real scoring deduction in practical loops.