Learn › DSA Patterns › Merge Intervals › Case Study

LeetCode 57 · Medium · Merge Intervals · TypeScript

Insert Interval:
Three Zones, One Pass

This one was accepted on the first submission. So instead of a bug log, here's the trace that proves why it works — and three tiny edits that would have broken it, each one actually run.

Scroll to follow the journey

The Problem

LeetCode 57 — Insert Interval

You get a list of non-overlapping intervals, sorted by start, and one newInterval. Insert it so the list stays sorted and non-overlapping, merging wherever needed. Two intervals overlap if they share at least one point — remember that sentence.

Input

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

Output

[[1,5],[6,9]]

Input

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

Output

[[1,2],[3,10],[12,16]]

Before the Code

The One Hint That Cracked It

No sorting needed — the input is already sorted. The hint was to draw Example 2 on a number line and ask where each interval sits relative to the new one.

 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
[1--2]
      [3-----5]
               [6--7]
                     [8------10]
                                    [12--------16]
          new: [4-----------8]

Left zone

end < newStart

Ends before the new one starts. Copy it as-is.

Overlap zone

neither check passes

Touches the new one. Absorb it — stretch both ends.

Right zone

start > newEnd

Starts after the new one ends. Copy it as-is.

The question that mattered most: where does [8,10] go? It only touches [4,8] at 8. Because touching counts, it belongs in the overlap zone — and that single fact decides both comparison operators.

The Journey

The Solution, and How to Break It

Card 1 is the code that was submitted. Cards 2–4 change one comparison or drop one line, and every output shown was produced by running it — not predicted.

1 The Submitted Solution — Accepted First Try ✅ Correct
function insert(intervals: number[][], newInterval: number[]): number[][] {
    let [newStart, newEnd] = newInterval
    let left = []; let right = []
    for(let [start, end] of intervals) {
        if(end<newStart) left.push([start, end])
        else if(start>newEnd) right.push([start,end])
        else {
            newStart = Math.min(start, newStart)
            newEnd = Math.max(end,newEnd)
        }
    }
    return [...left, [newStart, newEnd], ...right]
};

Written after a single hint: every existing interval sits entirely left of the new one, entirely right of it, or overlaps it. Left intervals are copied as-is. Right intervals are copied as-is. Overlapping ones get absorbed by stretching newStart down and newEnd up. The two highlighted comparisons are the whole problem — and both are strict.

Proof — node output on both LeetCode examples:

insert([[1,3],[6,9]], [2,5])
  → [[1,5],[6,9]]                 ✅ matches
insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])
  → [[1,2],[3,10],[12,16]]        ✅ matches
2 What If: start >= newEnd 🐛 Breaks
for (const [start, end] of intervals) {
    if (end < newStart) left.push([start, end])
    else if (start >= newEnd) right.push([start, end])
    else {
        newStart = Math.min(start, newStart)
        newEnd = Math.max(end, newEnd)
    }
}

One extra character on the right-zone check, and the second example breaks.

[8,10] and [4,8] share exactly one point: 8. The problem says that counts as overlapping. With >=, the check 8 >= 8 is true, so [8,10] is filed under 'right' and copied untouched — next to a merged block that already ends at 8.

Proof — node output, Example 2:

insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])
  → [[1,2],[3,8],[8,10],[12,16]]
Expected [[1,2],[3,10],[12,16]] ❌  — [3,8] and [8,10] touch but were never merged
Fix →

Keep it strict: start > newEnd. An interval is only fully right if it starts after the new one ends.

3 What If: end <= newStart — Passes Both Examples 🐛 Breaks
for (const [start, end] of intervals) {
    if (end <= newStart) left.push([start, end])
    else if (start > newEnd) right.push([start, end])
    else {
        newStart = Math.min(start, newStart)
        newEnd = Math.max(end, newEnd)
    }
}

The sneakier mirror image. Both LeetCode examples still pass, so you only find out on submit.

Neither official example has an interval that ends exactly where the new one starts. So the broken left check never fires on them. The smallest input that exposes it is a single interval touching the new one from the left.

Proof — node output:

insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])
  → [[1,2],[3,10],[12,16]]        ✅ still passes
insert([[1,4]], [4,6])
  → [[1,4],[4,6]]
Expected [[1,6]] ❌
Fix →

Keep it strict: end < newStart. Then add a 'touching on the left' and a 'touching on the right' case to your own tests — the examples don't cover either side.

4 What If: Only Stretch the End 🐛 Breaks
for (const [start, end] of intervals) {
    if (end < newStart) left.push([start, end])
    else if (start > newEnd) right.push([start, end])
    else {
        // newStart never moves
        newEnd = Math.max(end, newEnd)
    }
}

A merge that only grows rightward silently deletes part of the input.

It is tempting to think the new interval only ever extends to the right, because you're 'inserting' it. But [3,5] starts before [4,8]. Absorbing it has to pull the start down to 3, or the point 3 — covered in the input — vanishes from the output.

Proof — node output, Example 2:

insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])
  → [[1,2],[4,10],[12,16]]
Expected [[1,2],[3,10],[12,16]] ❌  — 3 is missing
Fix →

Widen both ends on every overlap: newStart = Math.min(start, newStart) and newEnd = Math.max(end, newEnd).

5 Polish — Type the Arrays You Return ✅ Correct
// LeetCode 57 — O(N) time, O(N) space (the output)
function insert(intervals: number[][], newInterval: number[]): number[][] {
  let [newStart, newEnd] = newInterval;
  const left: number[][] = [];
  const right: number[][] = [];

  for (const [start, end] of intervals) {
    if (end < newStart) left.push([start, end]);        // fully left
    else if (start > newEnd) right.push([start, end]); // fully right
    else {                                            // overlap: absorb it
      newStart = Math.min(start, newStart);
      newEnd = Math.max(end, newEnd);
    }
  }
  return [...left, [newStart, newEnd], ...right];
}

The submitted let left = [] is not a bug. TypeScript's evolving-array rule types it from the push calls, and strict mode accepts it. The change is about the reader: const says these arrays are never reassigned, and number[][] says what goes in them before you've read the loop.

Proof — tsc 6.0.3 and node:

tsc --strict --noEmit (original, let left = [])  → exit 0, no errors
insert([], [5,7])              → [[5,7]]          ✅ empty list
insert([[3,5]], [1,2])         → [[1,2],[3,5]]    ✅ new goes first
insert([[1,2]], [3,5])         → [[1,2],[3,5]]    ✅ new goes last
insert([[2,3],[5,6]], [1,10])  → [[1,10]]         ✅ swallows everything

Interactive

Zone Visualizer

Step through Example 2: [[1,2],[3,5],[6,7],[8,10],[12,16]] with [4,8]. Watch the bottom bar grow.

intervals new 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Start: newStart = 4, newEnd = 8. Every interval is still unclassified.

not checked yet kept (left or right) absorbed (overlap) new interval
Step Interval end < newStart start > newEnd Zone Action New interval after
1 [1,2] 2 < 4 ✅ – Left left = [[1,2]] [4, 8]
2 [3,5] 5 < 4 ❌ 3 > 8 ❌ Overlap min(3,4) = 3 [3, 8]
3 [6,7] 7 < 3 ❌ 6 > 8 ❌ Overlap nothing grows [3, 8]
4 [8,10] 10 < 3 ❌ 8 > 8 ❌ Overlap max(10,8) = 10 [3, 10]
5 [12,16] 16 < 3 ❌ 12 > 10 ✅ Right right = [[12,16]] [3, 10]

Step 4 is the one that matters: 8 > 8 is false, so [8,10] is absorbed. Notice also that newEnd grows to 10 before step 5 runs, so step 5 compares against 10, not 8.

Lessons Learned

Key Takeaways

🧭

Three zones, decided by two strict comparisons

Left means end < newStart. Right means start > newEnd. Everything else overlaps. Once those two lines are right, the rest of the function is bookkeeping.

📍

'Share at least one point' decides < versus <=

The problem defines touching intervals as overlapping. That single sentence is what makes both checks strict. Other interval problems define it the other way — always reread it.

🧪

The official examples don't test both edges

Changing the left check to <= still passes both LeetCode examples. Write your own touching-left and touching-right cases before you submit, not after a wrong answer.

↔️

A merge grows in both directions

Absorbing an interval can pull the start earlier as well as push the end later. Math.min on the start and Math.max on the end, every time.

⚡

Sorted input is a gift — don't re-sort it

Appending and running Merge Intervals works, but it pays O(N log N) for order you already had. The zone loop is O(N) because it trusts the input's guarantee.

Final Result

Two Correct Solutions

Both return the right answer. Only one uses what the problem gave you.

Fallback — Append, Sort, Merge
// O(N log N) — throws away the sorted guarantee
function insert(intervals: number[][], newInterval: number[]): number[][] {
  const all = [...intervals, newInterval]
    .sort((a, b) => a[0] - b[0]);
  const merged: number[][] = [];

  for (const [start, end] of all) {
    const last = merged[merged.length - 1];
    if (last && start <= last[1]) last[1] = Math.max(last[1], end);
    else merged.push([start, end]);
  }
  return merged;
}
Three Zones — This Journey's Result
// LeetCode 57 — O(N) time, O(N) space (the output)
function insert(intervals: number[][], newInterval: number[]): number[][] {
  let [newStart, newEnd] = newInterval;
  const left: number[][] = [];
  const right: number[][] = [];

  for (const [start, end] of intervals) {
    if (end < newStart) left.push([start, end]);        // fully left
    else if (start > newEnd) right.push([start, end]); // fully right
    else {                                            // overlap: absorb it
      newStart = Math.min(start, newStart);
      newEnd = Math.max(end, newEnd);
    }
  }
  return [...left, [newStart, newEnd], ...right];
}
Solution Time Space Why
Append + Sort + Merge O(N log N) O(N) Re-sorts input that was already sorted
Three Zones Optimal ✓ O(N) O(N) One pass, O(1) work per interval; the output itself is O(N)

Edge cases, all checked

Case intervals, newInterval Result
Empty list [], [5,7] [[5,7]]
New interval goes first [[3,5]], [1,2] [[1,2],[3,5]]
New interval goes last [[1,2]], [3,5] [[1,2],[3,5]]
Swallows everything [[2,3],[5,6]], [1,10] [[1,10]]
Touching on the left [[1,4]], [4,6] [[1,6]]

Reuse This

Template: Insert Into Sorted Intervals

The generic shape — adapt the two comparisons to however the problem defines overlap.

Pseudocode
function insert(sortedIntervals, [s, e]):
    left, right = [], []
    for [a, b] in sortedIntervals:
        if b < s:   left.append([a, b])     // strictly before
        elif a > e: right.append([a, b])    // strictly after
        else:                               // touches or overlaps
            s = min(s, a)
            e = max(e, b)
    return left + [[s, e]] + right

When to reach for this

The input is already sorted and non-overlapping, and one new range has to go in — a calendar booking, an IP range added to an allowlist, a new row in a range table.

The trap this journey avoided

Writing <= or >= in either zone check. One version fails Example 2; the other passes every example and fails on submit.

This is the sorted-input cousin of LeetCode 56. See the Merge Intervals pattern for the unsorted version, a merge visualizer, and the other ways interviewers disguise this problem.

Test Yourself

Quiz: Check Your Understanding

Question 1 of 6 Score: 0
In LeetCode 57, every existing interval [start, end] is compared against the new interval [newStart, newEnd]. Which pair of conditions correctly sends an interval to the left zone and the right zone, given that intervals sharing a single point count as overlapping? basic

Keep Learning

Accepted first try 🎉

Two strict comparisons and a min/max. The hard part was never the loop — it was deciding where a single touching point belongs.