DSAPrep
MediumIntervals

Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the ith 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.

Two intervals are considered overlapping if they share at least one point.

Insert newInterval into intervals such 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 intervals after the insertion.

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]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

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
View original on LeetCode ↗

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]:

Sorted intervals

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

Merged result

[1, 2]
1 / 5
mergingmerged

newInterval [4,8] starts at 4. [1,2] ends before that with no overlap, so copy it as-is.

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.