Learn › DSA Patterns › Merge Intervals › Case Study
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.
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.
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
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
Keep it strict: start > newEnd. An interval is only fully right if it starts after the new one ends.
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]] ❌
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.
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
Widen both ends on every overlap: newStart = Math.min(start, newStart) and newEnd = Math.max(end, newEnd).
// 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.
Start: newStart = 4, newEnd = 8. Every interval is still unclassified.
| 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.
// 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;
} // 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.
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
Your score
0 / 6
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.