Insert Interval

mediumGreedy & Intervals27 stepsJava · Python · C++

Insert a new interval into a sorted, non-overlapping list and merge as needed. Copy every interval that ends before the new one starts, merge every interval that overlaps it, then copy the rest.

▶ Watch the animated trace

Traced input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8] → [[1, 2], [3, 10], [12, 16]]. Original problem: neetcode.io/problems/insert-new-interval

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(n)

The input is already sorted, so no sort is needed.

Key idea

Phase 1: end < new.start → entirely before, copy it.
Phase 2: start <= new.end → overlaps, grow the new interval.
Phase 3: everything else is after, copy it.

Common mistakes

Re-sorting and running Merge Intervals works but is O(n log n).
Forgetting to add the merged new interval itself.

Solution

Java

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

Python

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    res, i, n = [], 0, len(intervals)
    lo, hi = newInterval
    while i < n and intervals[i][1] < lo:
        res.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= hi:
        lo = min(lo, intervals[i][0])
        hi = max(hi, intervals[i][1])
        i += 1
    res.append([lo, hi])
    res.extend(intervals[i:])
    return res

C++

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> res;
    int i = 0, n = intervals.size();
    vector<int> add = newInterval;
    while (i < n && intervals[i][1] < add[0]) {
        res.push_back(intervals[i]);
        i++;
    }
    while (i < n && intervals[i][0] <= add[1]) {
        add[0] = min(add[0], intervals[i][0]);
        add[1] = max(add[1], intervals[i][1]);
        i++;
    }
    res.push_back(add);
    while (i < n) {
        res.push_back(intervals[i]);
        i++;
    }
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Empty list Just the new interval.	`intervals = [], newInterval = [5, 7]`	`[[5, 7]]`
Insert at the end No overlap.	`intervals = [[1, 5]], newInterval = [6, 8]`	`[[1, 5], [6, 8]]`
Swallows everything Every interval is inside the new one.	`intervals = [[2, 3], [4, 5]], newInterval = [1, 9]`	`[[1, 9]]`