HARD Lab · Intervals · 48

57. Insert Interval

Scan sorted, non-overlapping intervals in three phases: pass the ones that end before the new interval starts, absorb every overlapping interval by expanding the new one, then pass the rest — all in a single O(n) sweep.

● MediumIntervalsMergeTypeScript

PROBLEM What we're solving

You have a sorted list of non-overlapping intervals and one new interval to insert. Return the merged list (still sorted, still non-overlapping). For example, [[1,3],[6,9]] with [2,5] inserted gives [[1,5],[6,9]] — the new interval overlaps [1,3], so they merge into [1,5], and [6,9] is untouched.

KEY IDEA Three non-overlapping phases, one pass

Insight → because the input is already sorted, every interval falls into exactly one of three categories relative to the new interval: entirely before it (copy as-is), overlapping with it (expand it), or entirely after it (copy as-is). Process them left-to-right in a single sweep — no sorting, no set structures needed.

RECIPE Skip · Merge · Append

  • 0 · Initialize. Start a result array and a pointer i = 0. The new interval tracks its current [start, end].
  • 1 · Skip (before). While intervals[i][1] < newInterval[0] (ends strictly before the new one starts), push unchanged and advance i.
  • 2 · Merge (overlap). While intervals[i][0] <= newInterval[1] (starts at or before the new one ends), expand: newInterval[0] = min(...), newInterval[1] = max(...). After the loop, push the expanded new interval.
  • 3 · Append (after). Push all remaining intervals unchanged. They start after the merged end so no overlap is possible.
Classic confusion → the overlap condition is intervals[i][0] <= newInterval[1] — note the <=. Two intervals [1,3] and [3,5] touch at 3 and must merge. Using strict < leaves them separate and produces invalid output.

COST Complexity & alternatives

Re-insert + sort + merge
O(n log n)
Sort destroys the sorted-input advantage.
Three-phase single pass
O(n)
O(n) time; O(n) output space (no extra structures).

Space note

The output array is O(n) in the worst case (no merges). There is no in-place version because the list may shrink (merges reduce count) or effectively grow (new interval between existing ones).

Pattern transfer → the same three-phase scan powers Merge Intervals (LC 56 — sort then scan), Meeting Rooms II (count concurrent overlaps), and Non-overlapping Intervals (greedy removal count). Any time intervals are sorted, look for a single left-to-right sweep.

RUN IT Skip · Merge · Append

step 0 / 4
STARTInsert 2-5 into [1-3, 6-9]. Three phases: skip intervals ending before new starts, merge overlapping ones, append the rest.
intervals + new1-36-92-5new
State
before
phase
2
mergeStart
5
mergeEnd
[]
result
current intervaloverlapping (being merged)merged/new intervaladded to result
slowfast

TYPESCRIPT The solution, annotated

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

  // Phase 1: add all intervals that end before newInterval starts
  while (i < n && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }

  // Phase 2: merge all overlapping intervals into newInterval
  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.push(newInterval);  // insert the (possibly expanded) interval

  // Phase 3: append remaining intervals unchanged
  while (i < n) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}

Reading it block by block

Lines 10–13 — Phase 1: skip.Any interval whose right end is strictly less than the new interval's left end cannot overlap. Push it straight to result. This condition, intervals[i][1] < newInterval[0], is why these intervals are safe to copy without touching newInterval.
Lines 16–20 — Phase 2: merge. An interval overlaps when its start is <= newInterval[1]. Each overlap forces an expansion: min on the left end, max on the right. After the loop the new interval has absorbed every overlapper, and is pushed once.
Lines 23–26 — Phase 3: append.The remaining intervals all start after the merged end. They're already sorted and non-overlapping; append without inspection.
Complexity → O(n) time — each interval is visited exactly once across the three phases. O(n) output space (the result list). No auxiliary data structures beyond the output array.

INTERVIEWFollow-ups they'll ask

  • "What if the list isn't sorted?" Sort first by start time (O(n log n)), then apply this exact three-phase scan. This is essentially Merge Intervals (LC 56).
  • "What if newInterval is already in the list?" Identical logic — the overlap phase catches it and merges it with itself. The output is the same.
  • "Can you do it in-place?" JavaScript arrays allow splice, but splice is O(n) per call and makes the code harder to reason about. For an interview, acknowledge the tradeoff and prefer the clean O(n) + O(n) version unless asked otherwise.
  • "Minimum number of interval removals to make non-overlapping?" Related greedy: sort by end, greedily keep intervals with the earliest end. Removal count = n − kept (LC 435).
  • "Trace [[1,2],[3,5],[6,7],[8,10]] with [4,8]" Phase 1 copies [1,2]; Phase 2 merges [3,5], [6,7], [8,10] into [3,10]; result is [[1,2],[3,10]].

MNEMONIC The one-liner

"Before goes straight, overlaps get eaten, after goes straight — insert once in the middle."

TRIGGERS When you see ___ → reach for ___

"insert into sorted non-overlapping intervals"three-phase single pass
overlap check for sorted intervalsstart ≤ other end (and vice versa)
"merge intervals" after sortingsame three-phase scan
expand a range greedilymin(starts), max(ends) inside the loop

SKELETON The reusable shape

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

  // Phase 1: before — ends before new starts
  while (i < n && intervals[i][1] < newInterval[0]) result.push(intervals[i++]);

  // Phase 2: overlap — starts before new ends → expand
  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.push(newInterval);

  // Phase 3: after — whatever remains
  while (i < n) result.push(intervals[i++]);

  return result;
}

FLASHCARDS Tap to flip

The three phases of insert-interval are…
(1) skip intervals ending before new starts, (2) merge all overlapping into new, (3) append rest.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 7
QUESTION 01
What is the time complexity of the three-phase single-pass solution?
QUESTION 02
Which condition checks that interval [a,b] overlaps with newInterval = [s,e] when scanning left to right (so a <= salready)?
QUESTION 03
Trace: intervals = [[1,3],[6,9]], newInterval = [2,5]. What is returned?
QUESTION 04
Why must the skip-phase condition be intervals[i][1] < newInterval[0](strict <)?
QUESTION 05
What happens when newInterval does not overlap any existing interval?
QUESTION 06
After the merge phase, result.push(newInterval) appears outside any loop. Why?
QUESTION 07
intervals = [[1,5]], newInterval = [0,6]. What is returned?