Insert Interval

The problem

intervals sorted by start, pairwise non-overlapping. Insert newInterval and return intervals still sorted and merged.

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

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

Brute

Push new interval, sort all, merge like Merge Intervals. O(n log n).

function insertBrute(intervals: number[][], newInterval: number[]): number[][] {
  const all = [...intervals, newInterval].sort((a, b) => a[0] - b[0]);
  const res: number[][] = [];
  for (const iv of all) {
    if (!res.length || res[res.length - 1][1] < iv[0]) res.push([...iv]);
    else res[res.length - 1][1] = Math.max(res[res.length - 1][1], iv[1]);
  }
  return res;
}

Optimal: one pass, three phases

Because input is sorted & non-overlapping:

1. Add all intervals ending before new starts.
2. Merge all that overlap new.
3. Add the rest.

function insert(intervals: number[][], newInterval: number[]): number[][] {
  const res: number[][] = [];
  let i = 0;
  const n = intervals.length;
  const ni = [...newInterval];

  // before
  while (i < n && intervals[i][1] < ni[0]) {
    res.push(intervals[i]);
    i++;
  }

  // overlap: interval starts <= ni end
  while (i < n && intervals[i][0] <= ni[1]) {
    ni[0] = Math.min(ni[0], intervals[i][0]);
    ni[1] = Math.max(ni[1], intervals[i][1]);
    i++;
  }
  res.push(ni);

  // after
  while (i < n) {
    res.push(intervals[i]);
    i++;
  }
  return res;
}

Time	O(n)
Space	O(n) output

Overlap condition

Two intervals [a,b], [c,d] overlap if a <= d && c <= b. Here sorted scan uses intervals[i][0] <= ni[1] after skipping those fully left.

Edge cases

• Empty intervals → [newInterval]
• New completely left or right
• New swallows all
• Touching endpoints: [1,2]+[2,3] → merge to [1,3] if closed intervals (LC merges when equal ends/starts)

Common mistakes

• Off-by-one on touching intervals
• Sorting when O(n) is available
• Mutating input newInterval without copy (ok if careful)

Interview delivery

1. Sorted non-overlapping input.
2. Three-phase scan.
3. Merge while overlapping.
4. Trace swallow-all case.
5. O(n).

Mental model

Because intervals are sorted and disjoint, the new interval overlaps a contiguous block (maybe empty). Stream left untouched intervals, merge the overlapping block into one, stream the right.

If the input weren’t sorted you’d fall back to full merge-intervals.

Touching endpoints

LC treats intervals as closed: [1,2] and [2,3] merge. Use intervals[i][0] <= new[1] not < only on open intervals.

Out-loud answer

“Three phases: push intervals fully left of new, merge while overlapping, push the rest. O(n) time. Sorting-all is correct but slower and ignores the given structure.”

Complexity table

Approach	Time	Space
Append + sort + merge	O(n log n)	O(n)
Three-phase scan	O(n)	O(n)

Interview delivery

1. Input sorted disjoint.
2. Left / merge / right.
3. Closed interval touching merges.
4. Empty list edge.
5. O(n).

Related

• Merge Intervals
• Non-overlapping Intervals
• Meeting Rooms
• Meeting Rooms II
• JavaScript Interview Guide

Further reading

• LeetCode 57 — Insert Interval
• Interval tree (optional deeper)