Insert Interval

Difficulty: Medium Source: NeetCode

Problem

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and end of the i-th interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals so that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return the resulting array of intervals.

Example 1: Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]

Example 2: Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]]

Constraints:

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^5
• intervals is sorted by start_i in ascending order
• newInterval.length == 2
• 0 <= start <= end <= 10^5

Prerequisites

Before attempting this problem, you should be comfortable with:

• Intervals — understanding how intervals overlap (two intervals [a,b] and [c,d] overlap if a <= d and c <= b)
• Greedy — making locally optimal choices (extend the merged interval as far right as possible)
• Arrays — iterating and building a result list

1. Brute Force

Intuition

Insert newInterval into the list, then re-sort by start time, then run the standard merge-intervals algorithm. It is simple and correct, but the sort costs extra time that we do not actually need since the input is already sorted.

Algorithm

1. Append newInterval to intervals.
2. Sort intervals by start time.
3. Initialize result with the first interval.
4. For each remaining interval, if it overlaps the last entry in result, extend that entry’s end. Otherwise append the interval to result.
5. Return result.

Solution

def insert_brute(intervals, newInterval):
    intervals.append(newInterval)
    intervals.sort(key=lambda x: x[0])

    result = [intervals[0]]
    for start, end in intervals[1:]:
        last_end = result[-1][1]
        if start <= last_end:
            result[-1][1] = max(last_end, end)
        else:
            result.append([start, end])
    return result


print(insert_brute([[1,3],[6,9]], [2,5]))          # [[1,5],[6,9]]
print(insert_brute([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]))  # [[1,2],[3,10],[12,16]]
print(insert_brute([], [5,7]))                     # [[5,7]]

Complexity

• Time: O(n log n) — dominated by the sort
• Space: O(n) — result list

2. Three-Phase Linear Scan

Intuition

Because the input is already sorted by start time, we can handle this in one pass without sorting. Think of it as three distinct phases: first, collect all intervals that end before the new interval starts (they can never overlap); second, merge all intervals that overlap with the new interval by extending it; third, collect everything that starts after the merged interval ends. This runs in O(n) time.

Algorithm

1. Initialize result = [] and i = 0.
2. Phase 1 — Add intervals before new one: While i < len(intervals) and intervals[i][1] < newInterval[0], append intervals[i] to result and advance i.
3. Phase 2 — Merge overlapping intervals: While i < len(intervals) and intervals[i][0] <= newInterval[1], expand newInterval to cover the union: newInterval[0] = min(newInterval[0], intervals[i][0]), newInterval[1] = max(newInterval[1], intervals[i][1]), advance i. Then append the merged newInterval.
4. Phase 3 — Add remaining intervals: Append intervals[i:] to result.
5. Return result.

Solution

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

    # Phase 1: intervals that end before newInterval starts — no overlap possible
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # Phase 2: merge all overlapping intervals into newInterval
    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)

    # Phase 3: intervals that start after newInterval ends — no overlap possible
    while i < n:
        result.append(intervals[i])
        i += 1

    return result


print(insert([[1,3],[6,9]], [2,5]))                          # [[1,5],[6,9]]
print(insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]))     # [[1,2],[3,10],[12,16]]
print(insert([], [5,7]))                                     # [[5,7]]
print(insert([[1,5]], [2,3]))                                # [[1,5]]
print(insert([[1,5]], [6,8]))                                # [[1,5],[6,8]]

Complexity

• Time: O(n) — single pass through the list
• Space: O(n) — result list

Common Pitfalls

Forgetting the edge case where the list is empty. When intervals = [], phases 1 and 3 are both skipped, and phase 2 just appends newInterval immediately — the code handles this naturally without a special case.

Off-by-one on overlap conditions. An interval [1,5] and newInterval = [5,7] DO overlap (they share the point 5). The condition for “no overlap before” is intervals[i][1] < newInterval[0] (strictly less), and for “overlapping” it is intervals[i][0] <= newInterval[1] (less than or equal).

Mutating the input. The merging step modifies newInterval in place. If the caller still needs the original newInterval, pass a copy instead.