Insert Interval (LeetCode 57)
You're handed an already-sorted, already-disjoint list of intervals intervals (each entry [start_i, end_i], ordered ascending by start_i), plus one more interval newInterval = [start, end] to drop into that list. Two intervals overlap the instant they share even a single point in common. Splice newInterval in, merging it with anything it touches, so the returned list is still start-sorted and still has no two entries overlapping. You may build and return a brand-new array instead of mutating intervals in place.
Worked Examples
intervals = [[1,3],[6,9]], newInterval = [2,5][[1,5],[6,9]][2,5] overlaps [1,3], so they merge into [1,5]; [6,9] stays as it is.intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8][[1,2],[3,10],[12,16]][4,8] touches [3,5], [6,7] and [8,10], so all four merge into [3,10].⚖️Formal Constraints & Bounds
0 <= intervals.length <= 104intervals[i].length == 20 <= start_i <= end_i <= 105intervalsis sorted bystart_iin ascending ordernewInterval.length == 20 <= start <= end <= 105
Core Insight
Single-pass three-phase partitioning eliminates the need to re-sort after insertion.
Real-World Scenario & Production Applications
Calendar scheduling engine appointment insertion, CPU task timeslot allocation.
Step-by-Step Execution Trace Table
| Phase | Processing Interval | Action | Result List |
|---|---|---|---|
| Phase 1 (Before) | [1, 3] | Overlaps [2, 5]: skip append | [] |
| Phase 2 (Overlap) | [1, 3] with [2, 5] | Fuse -> newInterval = [1, 5] | - |
| Append Fused | [1, 5] | Append fused interval | [[1, 5]] |
| Phase 3 (After) | [6, 9] | Starts after 5 -> append | [[1, 5], [6, 9]] |
| 1 | 1. Append intervals ending before newInterval starts |
| 2 | 2. Fuse all intervals overlapping with newInterval |
| 3 | 3. Append remaining intervals starting after newInterval ends |
Conceptual Narrative
Insert Interval splices a new interval into an already-sorted, non-overlapping list. A single-pass 3-phase partition merges overlapping spans in linear O(N) time with zero re-sorting.
🧭 Conceptual Foundation & Pattern Intuition
Unlike Merge Intervals where input is unsorted (), Insert Interval provides an array that is already sorted by start time and completely non-overlapping. Appending the new interval and re-sorting would waste the pre-existing order and cost . Exploiting the sorted, disjoint property allows a strict single-pass solution that partitions the timeline into three chronological phases:
- Phase 1 (Pre-Collision Disjoint): While
intervals[i][1] < newInterval[0], intervals end strictly beforenewIntervalbegins. They cannot overlap; append them verbatim. - Phase 2 (Overlapping Fusion): While
intervals[i][0] <= newInterval[1], intervals intersectnewInterval. Continually absorb them by expandingnewIntervalto[min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]. - Phase 3 (Post-Collision Disjoint): Append the single consolidated
newInterval, then append all remaining intervals verbatim (since they start strictly afternewIntervalends).
📥 The Analogy: Squeezing an Urgent Delivery Truck into a Train Schedule
Imagine a freight train schedule where every train has its own reserved track window and no two trains conflict. An emergency delivery train (newInterval) needs a window. You walk down the schedule: all morning trains that clear the station before your emergency train arrives run as normal (Phase 1). Any trains that would occupy the station while your train is present are consolidated into one unified priority block spanning the earliest arrival and latest departure (Phase 2). Once that unified block is locked in, all afternoon trains departure slots remain completely untouched (Phase 3).
🔑 Why It Works
Three simple non-nested while loops iterate through the list exactly once: each interval is inspected and appended at most once, guaranteeing optimal time and auxiliary space.
Re-sorting pre-sorted intervals: Appending
newIntervaland calling.sort()takes time, failing the time optimality constraint.Boundary condition on interval touch: Intervals that touch at a single point (e.g.
[1, 2]and[2, 5]) ARE overlapping. Overlap condition isintervals[i][0] <= newInterval[1], not<.Inserting at end or empty input: Forgetting to handle
intervals = []or whennewIntervalgoes at the very end of the list after all existing intervals.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Inserting a new range into an already sorted list of non-overlapping ranges.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: intervals are partitioned into strictly-before, overlapping, and strictly-after sets.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Index out of bounds on empty input.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Since intervals are sorted, I execute three linear phases: 1) append all intervals ending before
newInterval[0]; 2) while intervals overlap (start <= newInterval[1]), expandnewIntervalbounds; 3) appendnewIntervaland all remaining intervals. Runs inO(N)time andO(N)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Since intervals are already sorted, single linear pass adds all intervals ending before newInterval, merges overlapping intervals with newInterval, and appends remaining intervals. Total N steps.
O(N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Result array storing up to N + 1 merged intervals in O(N) space.
Derivation Progression
while intervals[i].end < new.start: res.append()
Appends pre-insertion intervals in O(1) each.
new = [min(starts), max(ends)]
Absorbs overlapping intervals into newInterval in O(1) each.
res.append(remaining)
Appends post-insertion intervals in O(1) each.
Variable Definitions
Total number of existing non-overlapping intervals
Memory Architecture & Bounds
O(1) Iterative
O(1) Scalar pointers (output array excluded)
O(N) Merged interval list
Boundary Best / Worst Cases
if prepended or appended outside range.
.
overlapping all intervals.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "insert newInterval into non-overlapping sorted intervals", "merge if necessary". The input is already sorted and disjoint! Junior candidates re-sort after inserting (). A Senior SWE preserves sorted structure in Linear Time via a 3-Phase Sweep: 1. Disjoint left intervals () 2. Overlapping intervals () 3. Disjoint right intervals ().
. Time budget is strictly . Memory budget is auxiliary to build the output array.
Single-loop pointer management must cleanly transition between phases.
Insert Interval (LeetCode 57)
You're handed an already-sorted, already-disjoint list of intervals intervals (each entry [start_i, end_i], ordered ascending by start_i), plus one more interval newInterval = [start, end] to drop into that list. Two intervals overlap the instant they share even a single point in common. Splice newInterval in, merging it with anything it touches, so the returned list is still start-sorted and still has no two entries overlapping. You may build and return a brand-new array instead of mutating intervals in place.
Worked Examples
intervals = [[1,3],[6,9]], newInterval = [2,5][[1,5],[6,9]][2,5] overlaps [1,3], so they merge into [1,5]; [6,9] stays as it is.intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8][[1,2],[3,10],[12,16]][4,8] touches [3,5], [6,7] and [8,10], so all four merge into [3,10].⚖️Formal Constraints & Bounds
0 <= intervals.length <= 104intervals[i].length == 20 <= start_i <= end_i <= 105intervalsis sorted bystart_iin ascending ordernewInterval.length == 20 <= start <= end <= 105
Core Insight
Single-pass three-phase partitioning eliminates the need to re-sort after insertion.
Real-World Scenario & Production Applications
Calendar scheduling engine appointment insertion, CPU task timeslot allocation.
Step-by-Step Execution Trace Table
| Phase | Processing Interval | Action | Result List |
|---|---|---|---|
| Phase 1 (Before) | [1, 3] | Overlaps [2, 5]: skip append | [] |
| Phase 2 (Overlap) | [1, 3] with [2, 5] | Fuse -> newInterval = [1, 5] | - |
| Append Fused | [1, 5] | Append fused interval | [[1, 5]] |
| Phase 3 (After) | [6, 9] | Starts after 5 -> append | [[1, 5], [6, 9]] |
| 1 | 1. Append intervals ending before newInterval starts |
| 2 | 2. Fuse all intervals overlapping with newInterval |
| 3 | 3. Append remaining intervals starting after newInterval ends |
Conceptual Narrative
Insert Interval splices a new interval into an already-sorted, non-overlapping list. A single-pass 3-phase partition merges overlapping spans in linear O(N) time with zero re-sorting.
🧭 Conceptual Foundation & Pattern Intuition
Unlike Merge Intervals where input is unsorted (), Insert Interval provides an array that is already sorted by start time and completely non-overlapping. Appending the new interval and re-sorting would waste the pre-existing order and cost . Exploiting the sorted, disjoint property allows a strict single-pass solution that partitions the timeline into three chronological phases:
- Phase 1 (Pre-Collision Disjoint): While
intervals[i][1] < newInterval[0], intervals end strictly beforenewIntervalbegins. They cannot overlap; append them verbatim. - Phase 2 (Overlapping Fusion): While
intervals[i][0] <= newInterval[1], intervals intersectnewInterval. Continually absorb them by expandingnewIntervalto[min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]. - Phase 3 (Post-Collision Disjoint): Append the single consolidated
newInterval, then append all remaining intervals verbatim (since they start strictly afternewIntervalends).
📥 The Analogy: Squeezing an Urgent Delivery Truck into a Train Schedule
Imagine a freight train schedule where every train has its own reserved track window and no two trains conflict. An emergency delivery train (newInterval) needs a window. You walk down the schedule: all morning trains that clear the station before your emergency train arrives run as normal (Phase 1). Any trains that would occupy the station while your train is present are consolidated into one unified priority block spanning the earliest arrival and latest departure (Phase 2). Once that unified block is locked in, all afternoon trains departure slots remain completely untouched (Phase 3).
🔑 Why It Works
Three simple non-nested while loops iterate through the list exactly once: each interval is inspected and appended at most once, guaranteeing optimal time and auxiliary space.
Re-sorting pre-sorted intervals: Appending
newIntervaland calling.sort()takes time, failing the time optimality constraint.Boundary condition on interval touch: Intervals that touch at a single point (e.g.
[1, 2]and[2, 5]) ARE overlapping. Overlap condition isintervals[i][0] <= newInterval[1], not<.Inserting at end or empty input: Forgetting to handle
intervals = []or whennewIntervalgoes at the very end of the list after all existing intervals.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Inserting a new range into an already sorted list of non-overlapping ranges.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: intervals are partitioned into strictly-before, overlapping, and strictly-after sets.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Index out of bounds on empty input.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Since intervals are sorted, I execute three linear phases: 1) append all intervals ending before
newInterval[0]; 2) while intervals overlap (start <= newInterval[1]), expandnewIntervalbounds; 3) appendnewIntervaland all remaining intervals. Runs inO(N)time andO(N)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Since intervals are already sorted, single linear pass adds all intervals ending before newInterval, merges overlapping intervals with newInterval, and appends remaining intervals. Total N steps.
O(N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Result array storing up to N + 1 merged intervals in O(N) space.
Derivation Progression
while intervals[i].end < new.start: res.append()
Appends pre-insertion intervals in O(1) each.
new = [min(starts), max(ends)]
Absorbs overlapping intervals into newInterval in O(1) each.
res.append(remaining)
Appends post-insertion intervals in O(1) each.
Variable Definitions
Total number of existing non-overlapping intervals
Memory Architecture & Bounds
O(1) Iterative
O(1) Scalar pointers (output array excluded)
O(N) Merged interval list
Boundary Best / Worst Cases
if prepended or appended outside range.
.
overlapping all intervals.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "insert newInterval into non-overlapping sorted intervals", "merge if necessary". The input is already sorted and disjoint! Junior candidates re-sort after inserting (). A Senior SWE preserves sorted structure in Linear Time via a 3-Phase Sweep: 1. Disjoint left intervals () 2. Overlapping intervals () 3. Disjoint right intervals ().
. Time budget is strictly . Memory budget is auxiliary to build the output array.
Single-loop pointer management must cleanly transition between phases.