Insert Interval

PracticeNeetCode ↗LeetCode ↗

Given a list of non-overlapping intervals sorted by start time, and a new interval, insert the new interval into the list — merging any intervals it overlaps with — and return the resulting non-overlapping, sorted list.

Example

Key Pointers

• Since the input is already sorted and non-overlapping, one linear pass is enough — no re-sorting needed.
• The walk naturally splits into three phases: intervals entirely before the new one, intervals that overlap and must merge into it, and intervals entirely after.
• Two intervals overlap exactly when one's start is not after the other's end.

Step-by-Step Analysis

1. Copy over every interval that ends strictly before newInterval starts — they need no merging.
2. While the current interval overlaps newInterval (its start is at or before newInterval's end), absorb it by extending newInterval's start/end to the min/max of the two.
3. Append the fully merged newInterval to the result.
4. Copy over every remaining interval unchanged — they all start after newInterval now ends.

Complexity

Time: O(n) — Space: O(n) for the output

Code

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

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

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

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

    return result

Code Explanation

How the solution above works, piece by piece.

1. The input is sorted and non-overlapping, so it splits into three groups: entirely before, overlapping, entirely after.
2. First loop: copy intervals that end before newInterval starts.
3. Second loop: while an interval starts before newInterval ends, they overlap; stretch newInterval to cover both. Then append it once.
4. Third loop: copy the rest.
5. One pass: O(n) time.

Visual Walkthrough

Running it on intervals = [[1, 3], [6, 9]], newInterval = [2, 5]:

Video Explanation

NeetCode — LeetCode 57