Insert Interval

Examples

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

[2,5] overlaps [1,3], so they merge into [1,5]. [6,9] is untouched.

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

[4,8] overlaps [3,5], [6,7], and [8,10], so all four intervals merge into [3,10].

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

With no existing intervals, the new one is simply inserted on its own.

Constraints

• 0 <= intervals.length <= 10^4

• intervals is sorted by start time and has no overlaps

• 0 <= start <= end <= 10^5

Approach

A quick way to solve this is to just add the new interval to the pile, sort everything by start time, and then merge overlapping neighbors — the same technique you'd use for a generic "merge all overlapping intervals" problem. It works, but it throws away the fact that the input was already sorted.

Since the list is already ordered and non-overlapping, you can do it in a single left-to-right pass: copy over every interval that ends before the new interval begins (they can't possibly overlap it), then absorb every interval that does overlap by growing the new interval's start and end to cover them, and finally copy over everything that's left.

Solutions

Brute Force — Sort and Merge

Treat this exactly like the general "merge overlapping intervals" problem: drop the new interval into the list, sort everything by start time, then walk through once, merging any interval into the last one in your result whenever they overlap.

function insert(intervals, newInterval) {
  const merged = [...intervals, newInterval];
  merged.sort((a, b) => a[0] - b[0]);

  const result = [];
  for (const interval of merged) {
    const last = result[result.length - 1];
    if (!last || last[1] < interval[0]) {
      result.push(interval);
    } else {
      last[1] = Math.max(last[1], interval[1]);
    }
  }
  return result;
}

Time: O(n log n) — dominated by the sort · Space: O(n) for the merged array and result

Optimal — Single Pass (Before / Overlap / After)

Because the input is already sorted and non-overlapping, you can skip sorting entirely. Walk through the intervals once:

- First, copy across any interval that ends before the new interval even starts — it can't overlap, so it goes straight into the answer. - Next, for every interval whose start is not past the new interval's current end, absorb it: shrink or grow the new interval's start/end to cover it. Keep doing this as long as intervals keep overlapping. - Once that stops, push the now-fully-merged new interval into the answer. - Finally, copy across everything that's left — none of it can overlap the new interval anymore.

function insert(intervals, newInterval) {
  const result = [];
  const n = intervals.length;
  let i = 0;
  let [start, end] = newInterval;

  while (i < n && intervals[i][1] < start) {
    result.push(intervals[i]);
    i++;
  }

  while (i < n && intervals[i][0] <= end) {
    start = Math.min(start, intervals[i][0]);
    end = Math.max(end, intervals[i][1]);
    i++;
  }
  result.push([start, end]);

  while (i < n) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}

Time: O(n) — one linear pass, no sorting needed · Space: O(n) for the result