Loading…

mediumIntervalsLC #57Frequently asked

Insert Interval

Q: How do you solve Insert Interval using the Append, Sort, Merge — Reuse Merge Intervals approach?

When to use it: Mention it as the 'I could just reduce this to a problem I already know' fallback — then point out it wastes the sorted input. Treat the problem as Merge Intervals with one extra element. Append `newInterval` to the list, sort the whole thing by start, then sweep left-to-right fusing any interval whose start is ≤ the previous interval's end. **Why reach for this first.** If you've already solved Merge Intervals, this is the lowest-risk path: you're reusing a routine you trust instead of writing new index gymnastics. In an interview it's a perfectly good thing to *say* — 'the safe version is to append and re-merge' — because it shows you can decompose a new problem into a known one. **Why it's not the answer they want.** The prompt hands you a list that is *already sorted and already non-overlapping*. Sorting it again throws that guarantee in the bin and pays `O(n log n)` for information you were given for free. The interviewer chose 'sorted input' on purpose — it's a flashing sign that an `O(n)` solution exists. Use this as the warm-up, then beat it. Time complexity: O(n log n). Space complexity: O(n).

Q: How do you solve Insert Interval using the Three-Phase Linear Sweep (Optimal) approach?

When to use it: The answer they want. Frame it as 'before / overlap / after' — three sequential loops over one index, no sort. Walk the list with a single index `i`, in three sequential phases. **Phase 1 — before.** While the current interval ends *strictly before* the new interval starts (`intervals[i][1] < newStart`), it can't possibly overlap, so copy it to the result untouched and advance. Because the input is sorted, once this stops, every remaining interval starts at or after this point. **Phase 2 — overlap.** While the current interval starts *at or before* the new interval ends (`intervals[i][0] <= newEnd`), it overlaps the (possibly already-grown) new interval. Don't append these — instead absorb them: `newStart = min(newStart, intervals[i][0])` and `newEnd = max(newEnd, intervals[i][1])`. The new interval swells to cover the whole overlapping run. When the loop ends, append the merged new interval exactly once. **Phase 3 — after.** Everything left starts strictly after the merged interval ends, so copy the remaining intervals verbatim. **Why three loops beat one branchy loop.** You *could* do this in a single loop with `if before / elif overlap / else after`, but the three-phase version makes the invariant obvious: each phase owns a contiguous slice of the sorted input, and the index only moves forward. It's easier to reason about and easier to get right under interview pressure. Time complexity: O(n). Space complexity: O(n).

LCPractice

Intervals · 1 of 7 · 8 min

You are given an array of non-overlapping intervals intervals where intervals[i] = [startᵢ, endᵢ] represent the start and end of the iᵗʰ interval, and intervals is sorted in ascending order by startᵢ.

You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by startᵢ and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

In plain English

You're handed a clean, sorted, gap-respecting timeline and one new event to drop in. Anything strictly to the left or right of the new event is untouched; anything that touches or overlaps it gets fused into one bigger interval. Return the timeline still sorted and still disjoint.

Examples

Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Note: [2,5] overlaps [1,3] (2 ≤ 3), so they merge into [1,5]. [6,9] starts after 5, untouched.

Example 2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Note: [4,8] overlaps [3,5], [6,7], and [8,10], fusing them into [3,10]. [1,2] is before, [12,16] is after.

Example 3

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Note: Nothing to merge with — the new interval is the whole answer.

Constraints

0 ≤ intervals.length ≤ 10⁴
intervals[i].length == 2
0 ≤ startᵢ ≤ endᵢ ≤ 10⁵
intervals is sorted by startᵢ in ascending order
newInterval.length == 2
0 ≤ start ≤ end ≤ 10⁵

Clarifying questions4First question: Is the input guaranteed sorted and non-overlapping?Explore questions

Q1.Is the input guaranteed sorted and non-overlapping?
Yes — that's the whole point. It lets us skip the sort and run a single O(n) pass.
Q2.Do touching intervals like [1,2] and [2,3] count as overlapping?
For this problem, yes — they should merge into [1,3]. If endpoints were exclusive we'd use strict inequality instead.
Q3.Can the new interval land before everything, after everything, or fill a gap with no overlap?
All three are valid. The three-phase structure handles 'no overlap' naturally — the overlap loop just runs zero times.
Q4.Can intervals be empty?
Yes — if intervals is empty we simply return [newInterval].

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

The input is already sorted and non-overlapping, so you don't need to re-sort. Walk the list once in three phases: copy every interval that ends before the new one starts, merge every interval that overlaps the new one into a single expanding interval, then copy the rest. That's O(n) time, O(n) output.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you notice the input is already sorted and exploit it for O(n), instead of blindly appending the new interval and re-running a full sort-and-merge.

Where candidates slip

Re-sorting the array (paying O(n log n) for nothing), or getting the overlap condition wrong so touching intervals like [1,2] and [2,3] don't merge.

How to stand out

State the three phases before coding, name the overlap test precisely (start <= end on both sides), and mention you could binary-search the insertion point to cut the 'before' scan to O(log n).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Append, Sort, Merge — Reuse Merge Intervals	`O(n log n)`	`O(n)`	Mention it as the 'I could just reduce this to a problem I already know' fallback — then point out it wastes the sorted input.	Read
2	Three-Phase Linear Sweep (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Frame it as 'before / overlap / after' — three sequential loops over one index, no sort.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewAdd an interval to a list of intervalsIs the input already sorted & disjoint?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Append, Sort, Merge — Reuse Merge Intervals

TimeO(n log n)SpaceO(n)

Mention it as the 'I could just reduce this to a problem I already know' fallback — then point out it wastes the sorted input.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already know how to merge a list of unsorted intervals. Can you turn this problem into that one?

2Hint 2Explore hint

Push newInterval onto the list, sort everything by start, then do the standard sweep-merge.

3Hint 3Explore hint

It works and it's easy to reason about — but ask yourself what the 'already sorted' guarantee was for.

A · Core idea

Treat the problem as Merge Intervals with one extra element. Append newInterval to the list, sort the whole thing by start, then sweep left-to-right fusing any interval whose start is ≤ the previous interval's end.

Why reach for this first. If you've already solved Merge Intervals, this is the lowest-risk path: you're reusing a routine you trust instead of writing new index gymnastics. In an interview it's a perfectly good thing to say — 'the safe version is to append and re-merge' — because it shows you can decompose a new problem into a known one.

Why it's not the answer they want. The prompt hands you a list that is already sorted and already non-overlapping. Sorting it again throws that guarantee in the bin and pays O(n log n) for information you were given for free. The interviewer chose 'sorted input' on purpose — it's a flashing sign that an O(n) solution exists. Use this as the warm-up, then beat it.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

append

add [2,5]

State[[1,3],[6,9],[2,5]]

Final result[[1,5],[6,9]]

C · Code with teaching comments

Reference implementation previewpublic int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> all = new ArrayList<>(Arrays.asList(intervals)); all.add(newInterval); all.sort((a, b) -> Integer.compare(a[0], b[0])); List<int[]> merged = new ArrayList<>();Explore the full code

solution.javaJava

Append, Sort, Merge — Reuse Merge Intervals — reference

2 teaching notes

1
public int[][] insert(int[][] intervals, int[] newInterval) {
2
    List<int[]> all = new ArrayList<>(Arrays.asList(intervals));
3
    all.add(newInterval);
4
    // The O(n log n) line — and the wasteful one, since the input was already sorted.
5
    all.sort((a, b) -> Integer.compare(a[0], b[0]));
6
    List<int[]> merged = new ArrayList<>();
7
    for (int[] cur : all) {
8
        // Disjoint from the last kept interval → start a new one; otherwise extend.
9
        if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < cur[0]) {
10
            merged.add(cur);
11
        } else {
12
            merged.get(merged.size() - 1)[1] =
13
                Math.max(merged.get(merged.size() - 1)[1], cur[1]);
14
        }
15
    }
16
    return merged.toArray(new int[merged.size()][]);
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

Reducing a new problem to a solved one is a real skill — but only when you can't do better. Here the sorted-input guarantee is the tell that a linear solution is reachable, so this O(n log n) version is a stepping stone, not the destination.

ComplexityO(n log n) time, O(n) space — The sort dominates at O(n log n); the merge sweep is O(n). The sort is pure waste here because the input minus the new interval was already ordered.

E · Edge cases and pitfalls5intervals = [], newInterval = [5,7] — all_iv = [[5,7]]; sort is a no-op; merge appends it → returns [[5,7]].Explore edge cases

Edge cases handled

intervals = [], newInterval = [5,7]all_iv = [[5,7]]; sort is a no-op; merge appends it → returns [[5,7]].
intervals = [[1,5]], newInterval = [2,3]newInterval is fully contained; merge keeps [1,5] since max(5,3)=5 → [[1,5]].

Pitfalls

Mutating the input `intervals` array in place while sorting — copy first.
Using `<=` instead of `<` in the disjoint test merges touching intervals (here that's desired, but be deliberate).
Forgetting this re-sort is the whole inefficiency — don't present it as the final answer.

03.2

Approach 2 of 2 · Optimal

Three-Phase Linear Sweep (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Frame it as 'before / overlap / after' — three sequential loops over one index, no sort.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The list is already sorted and disjoint. What can you copy verbatim before you even look at the new interval?

2Hint 2Explore hint

Split the work into three contiguous regions: intervals entirely before the new one, intervals that overlap it, and intervals entirely after.

3Hint 3Explore hint

In the overlap region, keep expanding newInterval: newStart = min(newStart, cur.start), newEnd = max(newEnd, cur.end). Append it once when overlapping stops, then copy the rest.

A · Core idea

Walk the list with a single index i, in three sequential phases.

Phase 1 — before. While the current interval ends strictly before the new interval starts (intervals[i][1] < newStart), it can't possibly overlap, so copy it to the result untouched and advance. Because the input is sorted, once this stops, every remaining interval starts at or after this point.

Phase 2 — overlap. While the current interval starts at or before the new interval ends (intervals[i][0] <= newEnd), it overlaps the (possibly already-grown) new interval. Don't append these — instead absorb them: newStart = min(newStart, intervals[i][0]) and newEnd = max(newEnd, intervals[i][1]). The new interval swells to cover the whole overlapping run. When the loop ends, append the merged new interval exactly once.

Phase 3 — after. Everything left starts strictly after the merged interval ends, so copy the remaining intervals verbatim.

Why three loops beat one branchy loop. You could do this in a single loop with if before / elif overlap / else after, but the three-phase version makes the invariant obvious: each phase owns a contiguous slice of the sorted input, and the index only moves forward. It's easier to reason about and easier to get right under interview pressure.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

before

[1,2] ends at 2 < 4 → copy

i ↓

[1,2]

[0]

[3,5]

[1]

[6,7]

[2]

[8,10]

[3]

[12,16]

[4]

Current pointerResolved stateNot processed

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

C · Code with teaching comments

solution.javaJava

Three-Phase Linear Sweep (Optimal) — optimal

4 teaching notes

1
public int[][] insert(int[][] intervals, int[] newInterval) {
2
    List<int[]> res = new ArrayList<>();
3
    int i = 0, n = intervals.length;
4
    int newStart = newInterval[0], newEnd = newInterval[1];
5
    // Phase 1 — interval ends before new one starts → cannot overlap, copy it.
6
    while (i < n && intervals[i][1] < newStart) {
7
        res.add(intervals[i]);
8
        i++;
9
    }
10
    // Phase 2 — interval starts at or before new end → overlaps, absorb instead of
11
    // copy.
12
    while (i < n && intervals[i][0] <= newEnd) {
13
        newStart = Math.min(newStart, intervals[i][0]);
14
        // Grow the new interval's right edge to swallow this overlapper.
15
        newEnd = Math.max(newEnd, intervals[i][1]);
16
        i++;
17
    }
18
    // Append the fully-merged interval ONCE, after the overlap run ends.
19
    res.add(new int[]{newStart, newEnd});
20
    while (i < n) {
21
        res.add(intervals[i]);
22
        i++;
23
    }
24
    return res.toArray(new int[res.size()][]);
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

The sorted, disjoint guarantee means the answer is naturally partitioned into three contiguous blocks: untouched-left, one fused middle, untouched-right. The only 'work' is fusing the middle — and fusing is just running min over starts and max over ends. Spot that partition and the code writes itself. If you wanted to shave the 'before' phase to O(log n), binary-search for the first interval whose end ≥ newStart — but the copy still makes the whole thing O(n), so it rarely matters.

ComplexityO(n) time, O(n) space — Each interval is visited by exactly one of the three loops, doing O(1) work — so O(n) time. Output holds up to n+1 intervals → O(n) space.

E · Edge cases and pitfalls5intervals = [[1,3],[6,9]], newInterval = [2,5] — Before-phase copies nothing (1's end 3 ≥ 2); overlap absorbs [1,3] → [1,5]; [6,9] copied after → [[1,5],[6,9]].Explore edge cases

Edge cases handled

intervals = [[1,3],[6,9]], newInterval = [2,5]Before-phase copies nothing (1's end 3 ≥ 2); overlap absorbs [1,3] → [1,5]; [6,9] copied after → [[1,5],[6,9]].
intervals = [[1,5]], newInterval = [6,8]Before-phase copies [1,5] (5 < 6); overlap runs zero times; append [6,8] → [[1,5],[6,8]] (a gap-filling insert).

Pitfalls

Using `<=` in phase 1's test makes a touching interval skip the merge — phase 1 must be strict `<`.
Appending the new interval inside the overlap loop produces duplicates — append once after the loop.
Forgetting phase 3 drops every interval after the merge region.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> res = new ArrayList<>(); int i = 0, n = intervals.length; int newStart = newInterval[0], newEnd = newInterval[1]; while (i < n && intervals[i][1] < newStart) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Re-sorting the input you were handed sorted

The prompt guarantees the list is already sorted by start. Sorting again costs O(n log n) and signals you missed the entire reason the input was specified that way.

Explore the code comparison

Don't write this

all_iv = intervals + [newInterval]
all_iv.sort(key=lambda iv: iv[0])  # O(n log n) — wasted

Write this instead

# No sort. Walk once in three phases — O(n).
while i < n and intervals[i][1] < new_start:
    res.append(intervals[i]); i += 1

Appending the new interval inside the overlap loop

Each overlapping interval would push a copy of the (still-growing) new interval, producing duplicates. The merged interval is finalized only after the overlap run ends.

Explore the code comparison

Don't write this

while i < n and intervals[i][0] <= new_end:
    new_end = max(new_end, intervals[i][1])
    res.append([new_start, new_end])  # appends every iteration
    i += 1

Write this instead

while i < n and intervals[i][0] <= new_end:
    new_start = min(new_start, intervals[i][0])
    new_end = max(new_end, intervals[i][1])
    i += 1
res.append([new_start, new_end])  # once

Wrong inequality in the before-phase

Phase 1 must stop on the first interval that could touch the new one. Using `<=` lets a touching interval (end == newStart) slip into the copy-as-is phase and never merge.

Explore the code comparison

Don't write this

while (i < n && intervals[i][1] <= newStart) {  // skips a toucher
    res.add(intervals[i]); i++;
}

Write this instead

while (i < n && intervals[i][1] < newStart) {   // strict
    res.add(intervals[i]); i++;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Three-phase linear sweep over sorted, non-overlapping intervals

Code pattern to memorize

# 1) before:   while end_i < newStart:        keep interval
# 2) overlap:  while start_i <= newEnd:        new = [min(starts), max(ends)]
# 3) after:    append merged new, then keep the rest

Rules to remember

1The input is already sorted by start and non-overlapping — re-sorting is the rookie move that throws away the O(n) you were handed.
2Two intervals overlap iff a.start <= b.end AND b.start <= a.end. Touching endpoints ([1,2] and [2,3]) count as overlapping for this problem.
3While merging, grow the new interval in place: newStart = min(newStart, cur.start), newEnd = max(newEnd, cur.end).
4Append the merged interval once, after the overlap phase ends — not inside the loop.
5Three sequential while loops over the same index i is cleaner than one loop with branchy if/else — say that out loud.

Use this pattern when

Input intervals are already sorted and disjoint, and you insert/merge one new range
You want O(n) without paying for a sort
Calendar / booking 'add this slot and merge conflicts' framing
A single new interval, not a batch — batch turns it into Merge Intervals

Choose another pattern when

Intervals are unsorted → sort first, then it's Merge Intervals (LC 56)
You must insert many intervals → re-merge the whole set instead
You only need to know IF it overlaps, not the merged result → a single boolean scan
Endpoints are exclusive (`[1,2)` doesn't touch `[2,3)`) → flip the comparison to strict `<`

Interview takeaway

When an interval list arrives pre-sorted, the sort is a gift — spend it on a single linear pass. Insert Interval is the cleanest example of the three-phase 'before / overlap / after' sweep that also powers Merge Intervals and most calendar problems.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternThree-phase interval sweep on sorted input. Recognise it whenever you insert/merge into an already-ordered, disjoint interval list. Same 'before / overlap / after' partition powers Merge Intervals and most calendar-booking problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

Continue · Next problem

Merge Intervals

mediumIntervalsLC #57Frequently asked

Insert Interval

LCPractice

Intervals · 1 of 7 · 8 min

You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Return intervals after the insertion.

In plain English

Examples

Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Note: [2,5] overlaps [1,3] (2 ≤ 3), so they merge into [1,5]. [6,9] starts after 5, untouched.

Example 2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Note: [4,8] overlaps [3,5], [6,7], and [8,10], fusing them into [3,10]. [1,2] is before, [12,16] is after.

Example 3

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Note: Nothing to merge with — the new interval is the whole answer.

Constraints

0 ≤ intervals.length ≤ 10⁴
intervals[i].length == 2
0 ≤ startᵢ ≤ endᵢ ≤ 10⁵
intervals is sorted by startᵢ in ascending order
newInterval.length == 2
0 ≤ start ≤ end ≤ 10⁵

Clarifying questions4First question: Is the input guaranteed sorted and non-overlapping?Explore questions

Q1.Is the input guaranteed sorted and non-overlapping?
Yes — that's the whole point. It lets us skip the sort and run a single O(n) pass.
Q2.Do touching intervals like [1,2] and [2,3] count as overlapping?
For this problem, yes — they should merge into [1,3]. If endpoints were exclusive we'd use strict inequality instead.
Q3.Can the new interval land before everything, after everything, or fill a gap with no overlap?
All three are valid. The three-phase structure handles 'no overlap' naturally — the overlap loop just runs zero times.
Q4.Can intervals be empty?
Yes — if intervals is empty we simply return [newInterval].

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you notice the input is already sorted and exploit it for O(n), instead of blindly appending the new interval and re-running a full sort-and-merge.

Where candidates slip

Re-sorting the array (paying O(n log n) for nothing), or getting the overlap condition wrong so touching intervals like [1,2] and [2,3] don't merge.

How to stand out

State the three phases before coding, name the overlap test precisely (start <= end on both sides), and mention you could binary-search the insertion point to cut the 'before' scan to O(log n).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Append, Sort, Merge — Reuse Merge Intervals	`O(n log n)`	`O(n)`	Mention it as the 'I could just reduce this to a problem I already know' fallback — then point out it wastes the sorted input.	Read
2	Three-Phase Linear Sweep (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Frame it as 'before / overlap / after' — three sequential loops over one index, no sort.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Append, Sort, Merge — Reuse Merge Intervals

TimeO(n log n)SpaceO(n)

Mention it as the 'I could just reduce this to a problem I already know' fallback — then point out it wastes the sorted input.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already know how to merge a list of unsorted intervals. Can you turn this problem into that one?

2Hint 2Explore hint

Push newInterval onto the list, sort everything by start, then do the standard sweep-merge.

3Hint 3Explore hint

It works and it's easy to reason about — but ask yourself what the 'already sorted' guarantee was for.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

append

add [2,5]

State[[1,3],[6,9],[2,5]]

Final result[[1,5],[6,9]]

C · Code with teaching comments

solution.javaJava

Append, Sort, Merge — Reuse Merge Intervals — reference

2 teaching notes

1
public int[][] insert(int[][] intervals, int[] newInterval) {
2
    List<int[]> all = new ArrayList<>(Arrays.asList(intervals));
3
    all.add(newInterval);
4
    // The O(n log n) line — and the wasteful one, since the input was already sorted.
5
    all.sort((a, b) -> Integer.compare(a[0], b[0]));
6
    List<int[]> merged = new ArrayList<>();
7
    for (int[] cur : all) {
8
        // Disjoint from the last kept interval → start a new one; otherwise extend.
9
        if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < cur[0]) {
10
            merged.add(cur);
11
        } else {
12
            merged.get(merged.size() - 1)[1] =
13
                Math.max(merged.get(merged.size() - 1)[1], cur[1]);
14
        }
15
    }
16
    return merged.toArray(new int[merged.size()][]);
17
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.17 lines

D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n log n) time, O(n) space — The sort dominates at O(n log n); the merge sweep is O(n). The sort is pure waste here because the input minus the new interval was already ordered.

E · Edge cases and pitfalls5intervals = [], newInterval = [5,7] — all_iv = [[5,7]]; sort is a no-op; merge appends it → returns [[5,7]].Explore edge cases

Edge cases handled

intervals = [], newInterval = [5,7]all_iv = [[5,7]]; sort is a no-op; merge appends it → returns [[5,7]].
intervals = [[1,5]], newInterval = [2,3]newInterval is fully contained; merge keeps [1,5] since max(5,3)=5 → [[1,5]].

Pitfalls

Mutating the input `intervals` array in place while sorting — copy first.
Using `<=` instead of `<` in the disjoint test merges touching intervals (here that's desired, but be deliberate).
Forgetting this re-sort is the whole inefficiency — don't present it as the final answer.

03.2

Approach 2 of 2 · Optimal

Three-Phase Linear Sweep (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Frame it as 'before / overlap / after' — three sequential loops over one index, no sort.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The list is already sorted and disjoint. What can you copy verbatim before you even look at the new interval?

2Hint 2Explore hint

Split the work into three contiguous regions: intervals entirely before the new one, intervals that overlap it, and intervals entirely after.

3Hint 3Explore hint

In the overlap region, keep expanding newInterval: newStart = min(newStart, cur.start), newEnd = max(newEnd, cur.end). Append it once when overlapping stops, then copy the rest.

A · Core idea

Walk the list with a single index i, in three sequential phases.

Phase 3 — after. Everything left starts strictly after the merged interval ends, so copy the remaining intervals verbatim.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

before

[1,2] ends at 2 < 4 → copy

i ↓

[1,2]

[0]

[3,5]

[1]

[6,7]

[2]

[8,10]

[3]

[12,16]

[4]

Current pointerResolved stateNot processed

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

C · Code with teaching comments

solution.javaJava

Three-Phase Linear Sweep (Optimal) — optimal

4 teaching notes

1
public int[][] insert(int[][] intervals, int[] newInterval) {
2
    List<int[]> res = new ArrayList<>();
3
    int i = 0, n = intervals.length;
4
    int newStart = newInterval[0], newEnd = newInterval[1];
5
    // Phase 1 — interval ends before new one starts → cannot overlap, copy it.
6
    while (i < n && intervals[i][1] < newStart) {
7
        res.add(intervals[i]);
8
        i++;
9
    }
10
    // Phase 2 — interval starts at or before new end → overlaps, absorb instead of
11
    // copy.
12
    while (i < n && intervals[i][0] <= newEnd) {
13
        newStart = Math.min(newStart, intervals[i][0]);
14
        // Grow the new interval's right edge to swallow this overlapper.
15
        newEnd = Math.max(newEnd, intervals[i][1]);
16
        i++;
17
    }
18
    // Append the fully-merged interval ONCE, after the overlap run ends.
19
    res.add(new int[]{newStart, newEnd});
20
    while (i < n) {
21
        res.add(intervals[i]);
22
        i++;
23
    }
24
    return res.toArray(new int[res.size()][]);
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — Each interval is visited by exactly one of the three loops, doing O(1) work — so O(n) time. Output holds up to n+1 intervals → O(n) space.

Edge cases handled

intervals = [[1,3],[6,9]], newInterval = [2,5]Before-phase copies nothing (1's end 3 ≥ 2); overlap absorbs [1,3] → [1,5]; [6,9] copied after → [[1,5],[6,9]].
intervals = [[1,5]], newInterval = [6,8]Before-phase copies [1,5] (5 < 6); overlap runs zero times; append [6,8] → [[1,5],[6,8]] (a gap-filling insert).

Pitfalls

Using `<=` in phase 1's test makes a touching interval skip the merge — phase 1 must be strict `<`.
Appending the new interval inside the overlap loop produces duplicates — append once after the loop.
Forgetting phase 3 drops every interval after the merge region.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Re-sorting the input you were handed sorted

The prompt guarantees the list is already sorted by start. Sorting again costs O(n log n) and signals you missed the entire reason the input was specified that way.

Explore the code comparison

Don't write this

all_iv = intervals + [newInterval]
all_iv.sort(key=lambda iv: iv[0])  # O(n log n) — wasted

Write this instead

# No sort. Walk once in three phases — O(n).
while i < n and intervals[i][1] < new_start:
    res.append(intervals[i]); i += 1

Appending the new interval inside the overlap loop

Each overlapping interval would push a copy of the (still-growing) new interval, producing duplicates. The merged interval is finalized only after the overlap run ends.

Explore the code comparison

Don't write this

while i < n and intervals[i][0] <= new_end:
    new_end = max(new_end, intervals[i][1])
    res.append([new_start, new_end])  # appends every iteration
    i += 1

Write this instead

while i < n and intervals[i][0] <= new_end:
    new_start = min(new_start, intervals[i][0])
    new_end = max(new_end, intervals[i][1])
    i += 1
res.append([new_start, new_end])  # once

Wrong inequality in the before-phase

Phase 1 must stop on the first interval that could touch the new one. Using `<=` lets a touching interval (end == newStart) slip into the copy-as-is phase and never merge.

Explore the code comparison

Don't write this

while (i < n && intervals[i][1] <= newStart) {  // skips a toucher
    res.add(intervals[i]); i++;
}

Write this instead

while (i < n && intervals[i][1] < newStart) {   // strict
    res.add(intervals[i]); i++;
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Three-phase linear sweep over sorted, non-overlapping intervals

Code pattern to memorize

# 1) before:   while end_i < newStart:        keep interval
# 2) overlap:  while start_i <= newEnd:        new = [min(starts), max(ends)]
# 3) after:    append merged new, then keep the rest

Rules to remember

1The input is already sorted by start and non-overlapping — re-sorting is the rookie move that throws away the O(n) you were handed.
2Two intervals overlap iff a.start <= b.end AND b.start <= a.end. Touching endpoints ([1,2] and [2,3]) count as overlapping for this problem.
3While merging, grow the new interval in place: newStart = min(newStart, cur.start), newEnd = max(newEnd, cur.end).
4Append the merged interval once, after the overlap phase ends — not inside the loop.
5Three sequential while loops over the same index i is cleaner than one loop with branchy if/else — say that out loud.

Use this pattern when

Input intervals are already sorted and disjoint, and you insert/merge one new range
You want O(n) without paying for a sort
Calendar / booking 'add this slot and merge conflicts' framing
A single new interval, not a batch — batch turns it into Merge Intervals

Choose another pattern when

Intervals are unsorted → sort first, then it's Merge Intervals (LC 56)
You must insert many intervals → re-merge the whole set instead
You only need to know IF it overlaps, not the merged result → a single boolean scan
Endpoints are exclusive (`[1,2)` doesn't touch `[2,3)`) → flip the comparison to strict `<`

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

Continue · Next problem

Merge Intervals