Insert Interval

MediumMerge IntervalsBlind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given a list of non-overlapping intervals sorted by start, where intervals[i] = [start, end], and one more interval, newInterval. Insert newInterval so the list stays sorted by start with no overlaps, merging it with every interval it overlaps; intervals that only touch at an endpoint also merge. Return the resulting list. The original list may be empty, and you may build a new list instead of editing in place.

Examples

intervals = [[1,3],[6,9]], newInterval = [2,5] returns [[1,5],[6,9]]

newInterval (highlighted) merges with [1,3] into [1,5].

[2,5] overlaps [1,3] from 2 to 3, so they combine into [1,5]. It ends before [6,9] starts, so that interval is kept as is.

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] returns [[1,2],[3,10],[12,16]]

The highlighted [4,8] absorbs three intervals, giving [3,10].

[4,8] overlaps [3,5] and [6,7], and touches [8,10] at 8, so all four merge into [3,10]. [1,2] ends before 4 and [12,16] starts after 8, so both stay.

Constraints

0 <= intervals.length <= 10^4
intervals is sorted, non-overlapping.

Hints

Hint 1

The list is already sorted and non-overlapping, can you do this in a single pass without re-sorting?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Because the list is sorted and disjoint, it splits into three runs. Copy every interval that ends before newInterval starts. Then absorb every interval whose start is <= newInterval's end, widening newInterval to the smallest start and largest end seen. Append the widened newInterval, then copy the rest. It's a single pass, and the output holds up to n + 1 intervals.

Time

O(n)

Space

O(n)

Pitfall

An interval comes before newInterval only if its end < newInterval's start, and overlaps it if its start <= newInterval's end. Swapping < and <= leaves touching pairs like [1,2] and [2,3] unmerged.

Solutions

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0, n = intervals.length;
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i++]);
        }
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);
        while (i < n) result.add(intervals[i++]);
        return result.toArray(new int[0][]);
    }
}

class Solution:
    def insert(self, intervals, newInterval):
        result = []
        i, n = 0, 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