Insert Interval [Medium] — Single-Pass Three-Phase Algorithm

Problem Statement#

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi], sorted in ascending order by starti. You are also given a new interval newInterval = [start, end] that you must insert into this array.

Insert newInterval so that the intervals are still sorted and non-overlapping (merge overlapping intervals if necessary).

Return the array of intervals after the insertion.

Examples:

Input:  intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: [2,5] overlaps [1,3], so they merge into [1,5]. [6,9] stays.
 
Input:  intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: [4,8] overlaps [3,5],[6,7],[8,10] — all three merge into [3,10].
 
Input:  intervals = [], newInterval = [5,7]
Output: [[5,7]]
Explanation: Empty list — just return the new interval.
 
Input:  intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]
Explanation: newInterval fits entirely inside [1,5], result is just [1,5].

Constraints:

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^5
• intervals is sorted by starti in ascending order
• intervals does not contain any overlapping intervals

Why This Problem Matters#

Insert Interval is a high-signal interview problem because it forces you to reason precisely about interval relationships. At Google, Amazon, and Bloomberg, it shows up in system-design-adjacent coding rounds — the scenario often maps to real calendar scheduling, log file merging, or network packet reassembly.

The deeper reason interviewers love it: the naive approach (insert into sorted position, then run merge intervals) works but is O(n log n). A single O(n) sweep is possible because the list is already sorted, and recognizing that optimization separates good candidates from great ones.

More importantly, this problem teaches you the three-region mental model for any sorted interval list — a framework you will reuse on problems like Meeting Rooms, Employee Free Time, Interval List Intersections, and Data Stream as Disjoint Intervals. Internalizing Insert Interval means you understand interval geometry at a deep level.

The Three-Phase Algorithm Insight#

The core insight is that relative to newInterval, every existing interval belongs to exactly one of three non-overlapping regions:

Region 1 — Completely Before:   interval.end < newInterval.start
Region 2 — Overlapping:         NOT (before OR after), i.e., starts to merge
Region 3 — Completely After:    interval.start > newInterval.end

Because the original list is sorted by start, these three regions appear in order — all "before" intervals come first, then all "overlapping" intervals, then all "after" intervals. There is no interleaving. This is the key geometric fact that makes a linear scan correct.

Phase 1 — Copy Before: Walk the list and copy every interval whose end is strictly less than newInterval.start. These are completely to the left; no merging needed.

Phase 2 — Merge Overlapping: Keep merging while the current interval's start is at or before newInterval.end. Two intervals overlap if and only if their ranges intersect, which happens when neither is completely before nor completely after the other. Each time we merge, we take:

• The new left boundary as min(current.start, newInterval.start)
• The new right boundary as max(current.end, newInterval.end)

After the loop, newInterval has absorbed all overlapping intervals, and we push it once.

Phase 3 — Copy After: Copy every remaining interval unchanged.

The overlap condition deserves special attention. Two intervals [a, b] and [c, d] overlap if and only if a <= d AND c <= b. In Phase 1, we know current.end < newInterval.start means they do NOT overlap (current is strictly before). The moment that condition fails, we enter Phase 2. We stay in Phase 2 as long as current.start <= newInterval.end — if a current interval starts after our new interval ends, there is no overlap and we've exited the merge zone.

Visual Dry Run#

Let's trace through the second example carefully:

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

Phase 1 — Copy intervals that end before 4:

i=0: [1,2]  → 2 < 4? YES → copy to result
     result = [[1,2]], i=1
 
i=1: [3,5]  → 5 < 4? NO  → stop Phase 1

Phase 2 — Merge overlapping intervals (start <= 8):

i=1: [3,5]  → 3 <= 8? YES → merge
     newInterval = [min(4,3), max(8,5)] = [3, 8], i=2
 
i=2: [6,7]  → 6 <= 8? YES → merge
     newInterval = [min(3,6), max(8,7)] = [3, 8], i=3
 
i=3: [8,10] → 8 <= 8? YES → merge
     newInterval = [min(3,8), max(8,10)] = [3, 10], i=4
 
i=4: [12,16] → 12 <= 8? NO → stop Phase 2

Push merged newInterval: result = [[1,2], [3,10]]

Phase 3 — Copy remaining intervals:

i=4: [12,16] → copy
     result = [[1,2], [3,10], [12,16]]

Final output: [[1,2], [3,10], [12,16]] — correct.

Now let's trace an edge case — newInterval that fits entirely inside one existing interval:

intervals  = [[1,5]]
newInterval = [2,3]
result = []
i = 0

Phase 1: 1 end = 5, is 5 < 2? No. Phase 1 ends immediately.

Phase 2: [1,5], is 1 <= 3? Yes. Merge: newInterval = [min(2,1), max(3,5)] = [1,5], i=1.

Is i < 1? No. Phase 2 ends. Push [1,5].

Phase 3: nothing left.

Output: [[1,5]] — correct, the new interval was swallowed.

Common Mistakes#

Mistake 1 — Off-by-one on the overlap boundary condition.

The most common bug is writing intervals[i][1] <= newInterval[0] (with <=) in Phase 1. Consider newInterval = [3,5] and an existing interval [1,3]. Their endpoints touch — they share the point 3, so they ARE overlapping. The correct condition for Phase 1 is strict less-than: intervals[i][1] < newInterval[0]. If you use <=, you'd incorrectly copy [1,3] without merging, then separately push [3,5], producing [[1,3],[3,5]] instead of [[1,5]].

Mistake 2 — Forgetting to push the merged newInterval.

After Phase 2 ends, the merged newInterval must be pushed to the result. Beginners sometimes go straight from Phase 2 to copying "after" intervals, skipping this push. The result is missing the merged interval entirely. The fix is always: after exiting the Phase 2 loop, append newInterval unconditionally.

Mistake 3 — Using binary search to find the insert position then re-running merge.

A common overthought approach is to binary search for where newInterval belongs, insert it into the list, then run the standard Merge Intervals algorithm. This is O(n log n) overall (O(n) for the insert shift in a list) and requires writing two separate algorithms. The single-pass approach is simpler to code and asymptotically faster. In interviews, showing you see the O(n) solution immediately is a strong positive signal.

Mistake 4 — Modifying newInterval in place versus keeping a separate accumulator.

Some implementations try to track the merged region separately with mergedStart and mergedEnd variables. This works but creates confusion about which variable to update when. The cleaner pattern is to mutate newInterval[0] and newInterval[1] directly during Phase 2 — it naturally accumulates the correct boundaries and there is only one object to push at the end.

Mistake 5 — Not handling edge cases: empty input and no-overlap inserts.

When intervals is empty, the loop never runs and you just return [newInterval]. When newInterval comes before all existing intervals (e.g., newInterval = [0,1] with intervals = [[5,10]]), Phase 1 finds nothing, Phase 2 finds nothing, you push [0,1], then Phase 3 copies everything. Both cases are handled correctly by the three-phase structure without any special-case if-statements — a sign the algorithm is truly general.

Solutions#

Python#

def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
    result = []          # output list that we build up incrementally
    i = 0                # index pointer into the intervals list
    n = len(intervals)
 
    # ─── Phase 1: copy all intervals that end BEFORE newInterval starts ───────
    # "intervals[i][1] < newInterval[0]" means interval i is completely to the
    # left of newInterval — no overlap possible, safe to copy as-is.
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
 
    # ─── Phase 2: merge all overlapping intervals into newInterval ────────────
    # An interval overlaps with newInterval when it starts at or before
    # newInterval ends. We keep expanding newInterval's boundaries.
    while i < n and intervals[i][0] <= newInterval[1]:
        # Expand the left boundary if the current interval starts earlier
        newInterval[0] = min(newInterval[0], intervals[i][0])
        # Expand the right boundary if the current interval ends later
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
 
    # After absorbing all overlapping intervals, push the fully merged interval
    result.append(newInterval)
 
    # ─── Phase 3: copy all remaining intervals (they start after newInterval) ─
    # Python slice appending is equivalent to a while loop but more concise
    result.extend(intervals[i:])
 
    return result

Alternative — more Pythonic one-liner style (same logic):

def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
    result = []
    i, n = 0, len(intervals)
 
    # Phase 1: skip and collect non-overlapping intervals on the left
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
 
    # Phase 2: merge overlapping intervals
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval = [
            min(newInterval[0], intervals[i][0]),  # take the earlier start
            max(newInterval[1], intervals[i][1])   # take the later end
        ]
        i += 1
 
    result.append(newInterval)    # push merged result (always exactly once)
 
    # Phase 3: append the tail — all intervals after the merge zone
    return result + intervals[i:]

JavaScript#

/**
 * @param {number[][]} intervals - sorted non-overlapping intervals
 * @param {number[]} newInterval - interval to insert and merge
 * @return {number[][]}
 */
var insert = function(intervals, newInterval) {
    const result = [];        // output array
    let i = 0;                // current index into intervals
    const n = intervals.length;
 
    // ── Phase 1: copy intervals that are completely before newInterval ────────
    // Condition: current interval ends before newInterval starts (no overlap)
    while (i < n && intervals[i][1] < newInterval[0]) {
        result.push(intervals[i]);   // safe to copy — it cannot overlap
        i++;
    }
 
    // ── Phase 2: merge all overlapping intervals into newInterval ─────────────
    // Condition: current interval starts at or before newInterval ends
    // (meaning the two ranges share at least one point)
    while (i < n && intervals[i][0] <= newInterval[1]) {
        // Absorb the current interval: expand boundaries if needed
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);  // take earlier start
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);  // take later end
        i++;
    }
 
    // Push the fully merged newInterval exactly once
    result.push(newInterval);
 
    // ── Phase 3: copy all remaining intervals (completely after newInterval) ──
    while (i < n) {
        result.push(intervals[i]);
        i++;
    }
 
    return result;
};

Complexity Analysis#

Follow-up Questions#

These are real questions that have appeared in FAANG follow-up rounds after solving this problem.

Q1: What if the input intervals are NOT sorted by start?

You would need to sort first: O(n log n). After sorting, you can run Insert Interval normally. But now total complexity is O(n log n) dominated by the sort. Alternatively, this degrades to the classic Merge Intervals problem (LeetCode 56).

Q2: What if you have to perform many insertions (not just one)?

For k insertions into a list of n intervals, repeatedly calling the O(n) single-insertion algorithm gives O(k * n) total. A better structure is a balanced BST (like a sorted set in C++ or a SortedList in Python with sortedcontainers) that keeps intervals sorted and allows O(log n) insertion and O(log n) merge per operation.

Q3: Can you solve this with binary search to speed up Phase 1 and Phase 3?

Yes. You can binary search for the first interval that does NOT satisfy end < newInterval.start (to find the start of the merge zone) and binary search for the first interval that satisfies start > newInterval.end (to find the end of the merge zone). This makes Phase 1 and Phase 3 O(log n) pointer-finding plus O(n) copying. Total is still O(n) because you must copy the result. The constant factor improves but asymptotic complexity doesn't change.

Q4: How would you handle this as a streaming problem — intervals arrive one at a time?

This is LeetCode 715 — Range Module. The key change is you need a data structure (typically a balanced BST or sorted dictionary) that supports adding, removing, and querying ranges efficiently. The SortedList from sortedcontainers in Python, or a TreeMap in Java, is the standard tool for this variant.

Q5: What if intervals can have fractional or floating-point boundaries?

The algorithm is identical — the comparison operators work the same for floats. The only concern is floating-point precision for boundary-touching cases (e.g., does 0.1 + 0.2 == 0.3?). In practice, interviews expect you to note this risk and suggest using epsilon-based comparison or representing times as integers (e.g., milliseconds).

Q6: How do you merge intervals from two separate sorted lists (not insert one interval)?

This is the Interval List Intersections problem (LeetCode 986). You use a two-pointer approach on both lists simultaneously. The three-phase insight from Insert Interval is the foundation — you're essentially doing Phase 2 across two lists at once.

This Pattern Solves#

Understanding the three-phase interval sweep unlocks a family of problems:

The pattern to internalize: whenever you have a sorted list of non-overlapping intervals and need to add or remove a range, think three regions — before, overlapping, after — and sweep once.

Key Takeaways#

• LeetCode 57 — Insert Interval is a Medium asked at Google, Amazon, and Meta; a single O(n) pass through three phases (before, overlapping, after) is the optimal approach.
• The three phases never interleave: once you enter "overlapping", you can't go back to "before"; once in "after", you're done — exploit this monotonic ordering.
• Overlap condition: newInterval.start <= interval.end AND newInterval.end >= interval.start — missing either half causes incorrect merges.
• Absorb overlapping intervals into newInterval (expand start/end), don't push them to result — push newInterval exactly once after all overlaps.
• Time O(n), space O(n) for the result — each interval is processed exactly once.
• General pattern: maintain a single mutable accumulator and flush it once — applies to all merge-on-the-fly interval problems.
• The pre-sorted input is load-bearing: without it you'd need to sort first (O(n log n)) as in LC 56 Merge Intervals — always ask "is input sorted?" upfront.

The algorithm in three lines of logic:

1. Copy everything strictly before the new interval.
2. Greedily expand the new interval to absorb all overlaps.
3. Copy everything strictly after the new interval.

That's it. Master this mental model and you'll handle every interval problem an interviewer can throw at you.