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 into the list so that the result is still sorted by start and still non-overlapping — merging newInterval with any intervals it overlaps or touches. Return the resulting list.

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

Examples

• intervals = [[1,3],[6,9]], newInterval = [2,5] → [[1,5],[6,9]] — [2,5] overlaps [1,3], so they fuse; [6,9] is untouched.
• intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] → [[1,2],[3,10],[12,16]] — the new interval swallows [3,5], [6,7], and [8,10] into one block.
• 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 — the intended solution exploits that for a single O(n) pass rather than 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 the gift of sortedness: drop newInterval into the list, sort, and run the standard Merge Intervals sweep.

from typing import List

class Solution:
    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 constraints tell you the input is already sorted and non-overlapping — re-sorting 10^4 intervals to place one newcomer throws that structure away, 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. So the answer is: (untouched prefix) + (one merged interval) + (untouched suffix).

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

class Solution:
    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.