Insert Interval

Brute Force (Append, Sort, Merge)

Time O(n log n)Space O(n)

Treat this as a special case of Merge Intervals: append newInterval to the list, sort everything by start, then sweep and merge overlapping neighbors.

class Solution:
    def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
        all_intervals = intervals + [newInterval]
        all_intervals.sort(key=lambda iv: iv[0])
        merged = [all_intervals[0]]
        for start, end in all_intervals[1:]:
            last = merged[-1]
            if start <= last[1]:
                last[1] = max(last[1], end)
            else:
                merged.append([start, end])
        return merged

This works and is easy to reason about, but it throws away the fact that intervals arrives already sorted — sorting again costs O(n log n) when a single linear pass would do.

Three-Pass Linear Scan

OptimalTime O(n)Space O(n)

Since intervals is already sorted and non-overlapping, walk it in three phases: copy every interval that ends strictly before newInterval starts (no overlap possible), merge every interval that overlaps newInterval by expanding its bounds, then copy whatever is left (all of which starts strictly after the merged interval ends).

class Solution:
    def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
        result = []
        i, n = 0, len(intervals)
        start, end = newInterval

        while i < n and intervals[i][1] < start:
            result.append(intervals[i])
            i += 1

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

        while i < n:
            result.append(intervals[i])
            i += 1

        return result

Tracing intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]. Watch the pointer walk the row: amber is the interval being examined, indigo is the new interval absorbing overlaps, and the result list fills in as each phase seals.

Sorted intervals

[1, 2][3, 5][6, 7][8, 10][12, 16]

New interval

[4, 8]to insert

Result so far

nothing yet

1 / 7

comparingcurrentresultseen

Insert [4,8] into the sorted, non-overlapping list. Pass 1 copies every interval that ends before 4; pass 2 merges whatever overlaps; pass 3 copies the rest.

Why it’s correct: since the input is sorted and non-overlapping, once an interval’s start exceeds the growing merged interval’s end, every later interval (with an even larger start) can never overlap it either — so it is safe to seal the merge and copy the remainder untouched. Each interval is visited exactly once → O(n) time; the output holds at most n + 1 intervals → O(n) space.

Brute Force (Append, Sort, Merge)

Three-Pass Linear Scan

More Intervals practice