Insert Interval

Problem

You are given a list of closed intervals intervals, already sorted by start and pairwise non-overlapping, plus one extra closed interval newInterval. Insert newInterval so the result stays sorted by start and non-overlapping, merging newInterval with any intervals it overlaps or touches. Return the resulting list.

Intervals are closed on both ends: [1,3] and [3,5] share the point 3 and merge into [1,5].

Examples

• intervals = [[1,3],[6,9]], newInterval = [2,5] → [[1,5],[6,9]] — [2,5] overlaps [1,3], so they merge; [6,9] is unchanged.
• intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] → [[1,2],[3,10],[12,16]] — the new interval merges [3,5], [6,7], and [8,10] into one interval.
• intervals = [], newInterval = [5,7] → [[5,7]] — inserting into an empty list.

Constraints

• 0 <= len(intervals) <= 10^4
• 0 <= start <= end <= 10^5 for every interval, including newInterval
• intervals is sorted by start and non-overlapping

The input is already sorted, so the intended solution uses that for a single O(n) pass instead of re-sorting.

Think about it first

TL;DR

One linear three-phase scan (before / merge / after): O(n) time, O(n) space for the output.

Approach 1 — Brute force: append, sort, merge everything

Ignore that the input is sorted: add newInterval to the list, sort, and run the standard Merge Intervals sweep.

from typing import List

def insert(
    self, intervals: List[List[int]], newInterval: List[int]
) -> List[List[int]]:
    everything = intervals + [newInterval]
    everything.sort(key=lambda it: it[0])
    merged: List[List[int]] = []
    for start, end in everything:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Complexity: O(n log n) time, O(n) space.

It works, but the input is already sorted and non-overlapping. Re-sorting 10^4 intervals to place one new interval discards that structure, and an interviewer will ask for the linear pass.

Approach 2 — One-pass three-phase scan

The insight: because the input is sorted and disjoint, the intervals that overlap newInterval form one contiguous block. Everything before that block ends before newInterval starts; everything after it starts after newInterval ends. The answer is the untouched prefix, then one merged interval, then the untouched suffix.

flowchart LR
    A["Phase 1: before<br/>end &lt; ns<br/>copy as-is"] --> B["Phase 2: overlap<br/>start &le; ne<br/>merge into [ns, ne]"] --> C["Phase 3: after<br/>copy as-is"]

An interval [s, e] overlaps [ns, ne] (closed intervals) when s <= ne and ns <= e. Walking left to right, the three phases test cheaper conditions: e < ns (before), then s <= ne (overlapping), then the rest (after).

from typing import List

def insert(
    self, intervals: List[List[int]], newInterval: List[int]
) -> List[List[int]]:
    ns, ne = newInterval
    result: List[List[int]] = []
    i, n = 0, len(intervals)

    # Phase 1: intervals ending strictly before newInterval starts.
    while i < n and intervals[i][1] < ns:
        result.append(intervals[i])
        i += 1

    # Phase 2: absorb everything that overlaps or touches [ns, ne].
    while i < n and intervals[i][0] <= ne:
        ns = min(ns, intervals[i][0])
        ne = max(ne, intervals[i][1])
        i += 1
    result.append([ns, ne])

    # Phase 3: the untouched suffix.
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

Walkthrough on intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]:

1. Phase 1: [1,2] ends at 2 < 4 → copied. [3,5] ends at 5, not < 4 → stop. result = [[1,2]].
2. Phase 2: [3,5] starts at 3 <= 8 → absorb: ns = 3, ne = 8. [6,7] starts at 6 <= 8 → absorb: ne stays 8. [8,10] starts at 8 <= 8 → absorb: ne = 10. [12,16] starts at 12 <= 10? No → stop. Emit [3,10].
3. Phase 3: copy [12,16].
4. result = [[1,2],[3,10],[12,16]]. Matches the expected output.

Complexity: O(n) time — each interval is examined once; O(n) space for the output (or O(1) extra beyond it).

A binary-search variant exists (locate the overlap block’s two boundaries with bisect, then splice), but the output copy is O(n) anyway, so it buys nothing asymptotically — the three-phase scan is the canonical answer.

Common pitfalls

• Boundary strictness: phase 1 must use end < ns and phase 2 start <= ne. Flip either one and touching intervals like [3,5] vs [5,7] are handled wrong — closed intervals that share an endpoint must merge.
• Forgetting to emit the merged interval when phase 2 absorbs zero intervals (new interval sits in a gap, or the input is empty). The code above appends [ns, ne] unconditionally, which handles both.
• Updating only ne during absorption. The first overlapping interval may start before newInterval does, so ns = min(ns, start) is required too.
• Trying to do it with one combined condition per element instead of three phases — it becomes an if/elif tangle where the merged interval is easy to emit twice or never.

Pattern takeaway

When intervals arrive sorted and disjoint, anything you insert affects one contiguous window of them. Partition the list into before / overlapping / after, collapse the middle with min-start and max-end, and concatenate. This “three-phase absorb” is the linear-time replacement for re-sorting, and the same absorb step (min of starts, max of ends) is the core move of every merge-style intervals problem.