Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumintervals

Insert Interval

Problem (restated)

You are given a list of non-overlapping intervals sorted by start, plus a newInterval. Insert newInterval so the result stays sorted and non-overlapping (merge when needed).

Intuition

The input is already sorted. Walk once: copy intervals completely before the new one, merge everything that touches it, then copy the rest.

Approaches

Three-phase linear scan

Tested only

Time O(n)Space O(n)

Idea. Phase 1: append intervals with end < new.start. Phase 2: expand new while cur.start ≤ new.end. Phase 3: append remaining.

Walkthrough. intervals = [[1,3],[6,9]], new = [2,5] → merge into [1,5], then append [6,9] → [[1,5],[6,9]].

Trade-offs. No sort needed because the list is pre-sorted. Binary search for the first overlap is possible but does not improve asymptotic cost of the merge phase.

Solution

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

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

  // merge all that overlap newInterval
  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);

  // remaining intervals after the merged block
  while (i < n) {
    res.push([...intervals[i]!]);
    i++;
  }
  return res;
}

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

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

  // merge all that overlap newInterval
  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);

  // remaining intervals after the merged block
  while (i < n) {
    res.push([...intervals[i]!]);
    i++;
  }
  return res;
}

Template connection

Insert is merge with a single extra interval and a known sorted input. Same overlap rule as Merge Intervals.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?