Problem statement

You are given non-overlapping intervals sorted by start, and a newInterval. Insert newInterval so the result is still sorted and non-overlapping (merge where necessary), and return it.

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 <= 20
• 0 <= start <= end <= 100
• intervals is sorted and non-overlapping.

Hints for Insert Interval

1. Hint 1

   Three phases: intervals entirely before, the merge zone, intervals entirely after.

2. Hint 2

   In the merge zone, absorb every interval that overlaps the growing new interval.

How to solve Insert Interval

The existing intervals are already sorted and disjoint, so no sorting is needed. Walk them once and split into three phases: those that end before the new interval begins pass through untouched; those that overlap get absorbed into a growing interval; those that start after it ends pass through untouched too.

Approach

1. Copy every interval whose end is strictly less than newInterval start — they finish before the new one starts.
2. While an interval starts at or before the growing new interval's end, absorb it: take min of the starts and max of the ends.
3. Append the merged interval.
4. Copy every remaining interval unchanged.
5. The result stays sorted because the three phases are emitted in order.

Why it works

Because the input is sorted and disjoint, the intervals overlapping the new one form a contiguous run, so the three phases really are consecutive and one pass covers them. Absorbing with min/max is exactly the union of two overlapping intervals, and repeating it collapses the whole run into a single interval whose bounds are correct however the intervals nest.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Touching counts as overlapping — the absorb test is start <= newEnd, so [1,3] and [3,5] merge into [1,5].
• Take max of the ends when absorbing; a fully-nested interval must not shrink the result.
• An empty input list is valid: the answer is just the new interval.
• Do not re-sort — the input order is already correct and sorting only hides mistakes.

Reference solution

Python

from typing import List

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

Java

public static int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> out = new ArrayList<>();
    int start = newInterval[0], end = newInterval[1];
    int i = 0, n = intervals.length;
    while (i < n && intervals[i][1] < start) {
        out.add(new int[]{intervals[i][0], intervals[i][1]});
        i++;
    }
    while (i < n && intervals[i][0] <= end) {
        if (intervals[i][0] < start) start = intervals[i][0];
        if (intervals[i][1] > end) end = intervals[i][1];
        i++;
    }
    out.add(new int[]{start, end});
    while (i < n) {
        out.add(new int[]{intervals[i][0], intervals[i][1]});
        i++;
    }
    return out.toArray(new int[0][]);
}

C++

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    vector<vector<int>> out;
    int start = newInterval[0], end = newInterval[1];
    int i = 0, n = (int) intervals.size();
    while (i < n && intervals[i][1] < start) {
        out.push_back(vector<int>{intervals[i][0], intervals[i][1]});
        i++;
    }
    while (i < n && intervals[i][0] <= end) {
        if (intervals[i][0] < start) start = intervals[i][0];
        if (intervals[i][1] > end) end = intervals[i][1];
        i++;
    }
    out.push_back(vector<int>{start, end});
    while (i < n) {
        out.push_back(vector<int>{intervals[i][0], intervals[i][1]});
        i++;
    }
    return out;
}

JavaScript

var insert = function(intervals, newInterval) {
    const out = [];
    let ns = newInterval[0], ne = newInterval[1];
    let i = 0;
    while (i < intervals.length && intervals[i][1] < ns) out.push(intervals[i++]);
    while (i < intervals.length && intervals[i][0] <= ne) {
        ns = Math.min(ns, intervals[i][0]);
        ne = Math.max(ne, intervals[i][1]);
        i++;
    }
    out.push([ns, ne]);
    while (i < intervals.length) out.push(intervals[i++]);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium