Insert Interval

INTERVALS · MEDIUM

Builds on Day 29: Mock Interview Day (Merge Intervals)

Read that problem first if the sort-then-merge idea is new — this page reuses its general merge scan as the brute-force fallback below.

The problem

You’re given a list of non-overlapping intervals, already sorted by start time, plus one new interval. Insert the new interval into the list, merging any overlapping intervals so the result stays sorted and non-overlapping.

Solution 1: Brute force — concat, sort, general merge

If you forget (or don’t trust) that the input is already sorted, the safe fallback is: append the new interval to the list, sort everything by start time, then run the same general Merge Intervals scan. It’s correct, but the sort is pure waste — the list was already sorted before the new interval showed up.

the new interval    in the result

Press Play or Step to begin.

▶ Play⏭ Step↺ Reset🔀 Shuffle

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  const sorted = intervals.slice().sort((a, b) => a[0] - b[0]);
  const result = [sorted[0].slice()];
  for (let i = 1; i < sorted.length; i++) {
    const last = result[result.length - 1];
    const [start, end] = sorted[i];
    if (start <= last[1]) {
      last[1] = Math.max(last[1], end);
    } else {
      result.push([start, end]);
    }
  }
  return result;
}

function insertBruteForce(intervals, newInterval) {
  return mergeIntervals(intervals.concat([newInterval]));
}

Line by line:

• intervals.concat([newInterval]) — the new interval is just another entry now, no different treatment from any existing one.
• .sort((a, b) => a[0] - b[0]) re-sorts everything by start time. This is the wasted work — the original intervals array was already in this order.
• The merge loop is the standard Merge Intervals scan — start <= last[1] extends the running merged interval, otherwise a new one starts.

Complexity: O(n log n) time, O(n) space — sort plus one linear merge pass.

Solution 2: Optimal — one linear pass, no sort

Since intervals is guaranteed already sorted and non-overlapping, walk it once in three phases: copy every interval that ends before the new one starts, absorb every interval that overlaps the new one (growing it), then copy everything left over. No sort needed anywhere.

newInterval, growing as it absorbs overlaps    finalized in the result

Press Play or Step to begin.

▶ Play⏭ Step↺ Reset

function insertOptimal(intervals, newInterval) {
  const result = [];
  let i = 0;
  const n = intervals.length;
  let [ns, ne] = newInterval;

  // Phase 1: intervals ending strictly before the new interval starts — copy as-is.
  while (i < n && intervals[i][1] < ns) {
    result.push(intervals[i]);
    i++;
  }
  // Phase 2: intervals overlapping the new interval — absorb them into [ns, ne].
  while (i < n && intervals[i][0] <= ne) {
    ns = Math.min(ns, intervals[i][0]);
    ne = Math.max(ne, intervals[i][1]);
    i++;
  }
  result.push([ns, ne]);
  // Phase 3: everything after — copy as-is.
  while (i < n) {
    result.push(intervals[i]);
    i++;
  }
  return result;
}

Line by line:

• Phase 1’s condition intervals[i][1] < ns — strictly less than, so a touching interval like [1,2] against a new interval starting at 2 correctly falls through to phase 2 instead of being copied untouched.
• Phase 2 grows [ns, ne] with Math.min/Math.max — the merged interval always covers everything it has absorbed so far.
• The merged [ns, ne] is pushed exactly once, right when phase 2 ends — there’s no ambiguity about when merging stops, because the while condition itself is the stopping rule.
• Every interval is visited by exactly one phase — that’s what makes this O(n) instead of O(n log n).

Complexity: O(n) time, O(n) space — a 3-phase linear scan that exploits the sorted input.

Complexity comparison

Solution	Time	Space
Brute force (sort + general merge)	O(n log n)	O(n)
Optimal (3-phase linear scan)	O(n)	O(n)

Interview corner

What if newInterval doesn’t overlap anything?

• Phase 1 copies everything before it, unchanged.
• Phase 2 runs zero iterations — nothing overlaps.
• Phase 3 copies everything after it, unchanged.

⚠ Trap: phase 2’s overlap check uses <=, not < — touching intervals like [1,2] and [2,3] still count as overlapping and must merge into [1,3]. Strict < would silently leave two intervals that should have merged sitting side by side.

How would you extend this to DELETE an interval instead of inserting one?

• Walk the sorted array once.
• Skip any interval fully contained by the one being deleted.
• Split any interval that only partially overlaps it into up to two pieces.
• Copy everything untouched as-is.

↳ Common follow-up: “What if the deleted interval spans multiple existing intervals?” More than one gets split or removed in the same single pass — still one linear scan, just with an extra output branch.

Could you use binary search instead of a linear scan here?

• Binary search can find where the “before” phase ends (first interval whose end reaches or passes newInterval.start) in O(log n).
• But the overlap-absorbing and copy-remaining phases still have to touch every interval they cover.
• Overall worst case stays O(n) — binary search only speeds up locating the start of the work, not the total amount of work.

Trick question — what does this log?

const intervals = [[1, 3], [6, 9]];
const copy = intervals.slice();
copy[0][0] = 99;
console.log(intervals[0][0]);

• Answer: 99, not 1.
• .slice() only makes a shallow copy — the outer array is new, but each inner array ([1, 3], [6, 9]) is still the exact same object reference in both arrays.
• Mutating copy[0][0] mutates the shared inner array, which intervals[0] still points to.

⚠ Trap: this is exactly why the code above never mutates an interval directly — it always builds a fresh [start, end] pair before pushing it, so the caller’s original array is never silently corrupted.

Quiz

Quiz: 1. Why can the optimal solution skip sorting entirely?

intervals is guaranteed already sorted by start time as an input precondition

The problem guarantees intervals arrives already sorted by start time and non-overlapping — that precondition is exactly what the 3-phase scan relies on to skip sorting entirely.

Quiz: 2. In the optimal 3-phase scan, what determines when the “before” phase ends and the “overlapping” phase begins?

The current interval’s end is no longer strictly less than newInterval’s start

Phase 1 keeps copying untouched intervals as long as they end strictly before newInterval starts. The moment an interval’s end reaches or passes newInterval’s start, it overlaps and phase 2 begins.

Quiz: 3. What determines when the “overlapping” merge phase ends and the “after” phase begins?

The current interval’s start is greater than the merged newInterval’s end

As soon as an interval’s start is greater than the merged newInterval’s current end, there’s no more overlap left to absorb, so the merged interval is finalized and phase 3 begins.

Quiz: 4. Why does the brute-force sort+merge approach still work correctly even though it ignores the fact the input was already sorted?

Merge Intervals’ general algorithm correctly handles any unsorted input, sorted or not

Merge Intervals’ general algorithm doesn’t assume anything about how the input arrived — it just sorts and merges whatever it’s given, so appending the new interval and re-sorting still produces a correct result, just with an avoidable extra sort.

Quiz: 5. What’s the time complexity difference between the two solutions, and why?

Brute force O(n log n) from the sort; optimal O(n) with no sort needed

Brute force is O(n log n), dominated entirely by the sort step. Optimal is O(n), a single pass with no sort — because the 3-phase scan exploits the guarantee that the input arrives already sorted.