57. Insert Interval (Medium)

Problem

Given intervals sorted by start (non-overlapping) and a new newInterval, insert it into intervals such that the result is still non-overlapping (merge as necessary).

Example

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

LeetCode 57 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, append and merge

Add to list, sort, run Merge Intervals.

Python

def insert(intervals, new_interval):
    intervals = [list(iv) for iv in intervals] + [list(new_interval)]
    intervals.sort(key=lambda x: x[0])              # L1: O(n log n)
    result = []
    for iv in intervals:                             # L2: O(n) sweep
        if result and iv[0] <= result[-1][1]:
            result[-1][1] = max(result[-1][1], iv[1])
        else:
            result.append(list(iv))
    return result

TypeScript

function insert(intervals: number[][], newInterval: number[]): number[][] {
    const all = [...intervals.map(iv => [...iv]), [...newInterval]];
    all.sort((a, b) => a[0] - b[0]);                // L1: O(n log n)
    const result: number[][] = [];
    for (const iv of all) {                          // L2: O(n) sweep
        if (result.length > 0 && iv[0] <= result[result.length - 1][1]) {
            result[result.length - 1][1] = Math.max(result[result.length - 1][1], iv[1]);
        } else {
            result.push([...iv]);
        }
    }
    return result;
}

Go

func insert(intervals [][]int, newInterval []int) [][]int {
    all := make([][]int, len(intervals)+1)
    for i, iv := range intervals { all[i] = []int{iv[0], iv[1]} }
    all[len(intervals)] = []int{newInterval[0], newInterval[1]}
    sort.Slice(all, func(i, j int) bool { return all[i][0] < all[j][0] })  // L1: O(n log n)
    result := [][]int{}
    for _, iv := range all {                         // L2: O(n) sweep
        if len(result) > 0 && iv[0] <= result[len(result)-1][1] {
            if iv[1] > result[len(result)-1][1] { result[len(result)-1][1] = iv[1] }
        } else {
            result = append(result, []int{iv[0], iv[1]})
        }
    }
    return result
}

Swift

final class Solution {
    func insert(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
        let sorted = (intervals + [newInterval]).sorted { $0[0] < $1[0] }
        var result: [[Int]] = []
        for interval in sorted {
            if let last = result.last, interval[0] <= last[1] { result[result.count - 1][1] = max(last[1], interval[1]) }
            else { result.append(interval) }
        }
        return result
    }
}

The sort is the load-bearing step. After sort, the linear merge is the same template as LeetCode 56.

Complexity

• Time: $O(n log n)$.
• Space: $O(n)$.

Approach 2: Binary search for insertion point + left-merge + right-merge

Find where newInterval goes; then walk left and right, merging overlaps.

Python

import bisect

def insert(intervals, new_interval):
    intervals = [list(iv) for iv in intervals]
    starts = [iv[0] for iv in intervals]
    idx = bisect.bisect_left(starts, new_interval[0])  # L1: O(log n) search
    intervals.insert(idx, list(new_interval))           # L2: O(n) shift

    # Merge leftward while previous overlaps
    while idx > 0 and intervals[idx - 1][1] >= intervals[idx][0]:
        intervals[idx - 1][1] = max(intervals[idx - 1][1], intervals[idx][1])
        intervals.pop(idx)
        idx -= 1

    # Merge rightward while next overlaps
    while idx + 1 < len(intervals) and intervals[idx][1] >= intervals[idx + 1][0]:
        intervals[idx][1] = max(intervals[idx][1], intervals[idx + 1][1])
        intervals.pop(idx + 1)

    return intervals

TypeScript

function insert(intervals: number[][], newInterval: number[]): number[][] {
    const ivs = intervals.map(iv => [...iv]);
    // find insertion point by binary search
    let lo = 0, hi = ivs.length;
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (ivs[mid][0] < newInterval[0]) lo = mid + 1; else hi = mid;
    }
    let idx = lo;
    ivs.splice(idx, 0, [...newInterval]);               // L1/L2: O(n) shift

    // Merge leftward
    while (idx > 0 && ivs[idx - 1][1] >= ivs[idx][0]) {
        ivs[idx - 1][1] = Math.max(ivs[idx - 1][1], ivs[idx][1]);
        ivs.splice(idx, 1); idx--;
    }
    // Merge rightward
    while (idx + 1 < ivs.length && ivs[idx][1] >= ivs[idx + 1][0]) {
        ivs[idx][1] = Math.max(ivs[idx][1], ivs[idx + 1][1]);
        ivs.splice(idx + 1, 1);
    }
    return ivs;
}

Go

func insert(intervals [][]int, newInterval []int) [][]int {
    ivs := make([][]int, len(intervals))
    for i, iv := range intervals { ivs[i] = []int{iv[0], iv[1]} }
    // binary search for insertion point
    lo, hi := 0, len(ivs)
    for lo < hi {
        mid := (lo + hi) / 2
        if ivs[mid][0] < newInterval[0] { lo = mid + 1 } else { hi = mid }
    }
    idx := lo
    ivs = append(ivs[:idx], append([][]int{{newInterval[0], newInterval[1]}}, ivs[idx:]...)...)  // L1/L2: O(n) shift

    // Merge leftward
    for idx > 0 && ivs[idx-1][1] >= ivs[idx][0] {
        if ivs[idx][1] > ivs[idx-1][1] { ivs[idx-1][1] = ivs[idx][1] }
        ivs = append(ivs[:idx], ivs[idx+1:]...)
        idx--
    }
    // Merge rightward
    for idx+1 < len(ivs) && ivs[idx][1] >= ivs[idx+1][0] {
        if ivs[idx+1][1] > ivs[idx][1] { ivs[idx][1] = ivs[idx+1][1] }
        ivs = append(ivs[:idx+1], ivs[idx+2:]...)
    }
    return ivs
}

Swift

final class Solution {
    func insert(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
        var low = 0
        var high = intervals.count
        while low < high { let middle = (low + high) / 2; if intervals[middle][0] < newInterval[0] { low = middle + 1 } else { high = middle } }
        var values = intervals
        values.insert(newInterval, at: low)
        var result: [[Int]] = []
        for interval in values {
            if let last = result.last, interval[0] <= last[1] { result[result.count - 1][1] = max(last[1], interval[1]) }
            else { result.append(interval) }
        }
        return result
    }
}

The binary search saves work on the search, but the insert and pop calls are $O(n)$ shifts, so the worst case is the same as a single linear pass.

Same $O(n)$ in the worst case.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Single linear pass (canonical, $O(n)$)

Three phases over the sorted list:

1. Copy all intervals strictly before newInterval.
2. Merge any overlapping with newInterval.
3. Copy the rest.

Python

def insert(intervals, new_interval):
    result = []                   # L1: O(1) setup
    i = 0                         # L2: O(1)
    n = len(intervals)            # L3: O(1)

    # 1. before
    while i < n and intervals[i][1] < new_interval[0]:   # L4: O(1) per check
        result.append(intervals[i])                        # L5: O(1) per append
        i += 1

    # 2. overlap
    while i < n and intervals[i][0] <= new_interval[1]:  # L6: O(1) per check
        new_interval = [min(new_interval[0], intervals[i][0]),
                        max(new_interval[1], intervals[i][1])]  # L7: O(1) per merge
        i += 1
    result.append(new_interval)   # L8: O(1)

    # 3. after
    while i < n:                  # L9: O(1) per check
        result.append(intervals[i])  # L10: O(1) per append
        i += 1

    return result

TypeScript

function insert(intervals: number[][], newInterval: number[]): number[][] {
    const result: number[][] = [];                         // L1: O(1) setup
    let i = 0;                                            // L2: O(1)
    const n = intervals.length;                           // L3: O(1)

    // 1. before
    while (i < n && intervals[i][1] < newInterval[0]) {  // L4: O(1) per check
        result.push([...intervals[i]]);                   // L5: O(1) per append
        i++;
    }

    // 2. overlap
    while (i < n && intervals[i][0] <= newInterval[1]) { // L6: O(1) per check
        newInterval = [Math.min(newInterval[0], intervals[i][0]),
                       Math.max(newInterval[1], intervals[i][1])]; // L7: O(1) per merge
        i++;
    }
    result.push(newInterval);                             // L8: O(1)

    // 3. after
    while (i < n) {                                       // L9: O(1) per check
        result.push([...intervals[i]]);                   // L10: O(1) per append
        i++;
    }

    return result;
}

Go

func insert(intervals [][]int, newInterval []int) [][]int {
    result := [][]int{}                // L1: O(1) setup
    i := 0                             // L2: O(1)
    n := len(intervals)                // L3: O(1)

    // 1. before
    for i < n && intervals[i][1] < newInterval[0] {  // L4: O(1) per check
        result = append(result, []int{intervals[i][0], intervals[i][1]})  // L5: O(1) per append
        i++
    }

    // 2. overlap
    for i < n && intervals[i][0] <= newInterval[1] {  // L6: O(1) per check
        if intervals[i][0] < newInterval[0] { newInterval[0] = intervals[i][0] }
        if intervals[i][1] > newInterval[1] { newInterval[1] = intervals[i][1] }  // L7: O(1) per merge
        i++
    }
    result = append(result, []int{newInterval[0], newInterval[1]})  // L8: O(1)

    // 3. after
    for i < n {                        // L9: O(1) per check
        result = append(result, []int{intervals[i][0], intervals[i][1]})  // L10: O(1) per append
        i++
    }

    return result
}

Swift

final class Solution {
    func insert(_ intervals: [[Int]], _ newInterval: [Int]) -> [[Int]] {
        var result: [[Int]] = []
        var index = 0
        var merged = newInterval
        while index < intervals.count && intervals[index][1] < merged[0] { result.append(intervals[index]); index += 1 }
        while index < intervals.count && intervals[index][0] <= merged[1] { merged[0] = min(merged[0], intervals[index][0]); merged[1] = max(merged[1], intervals[index][1]); index += 1 }
        result.append(merged)
        result.append(contentsOf: intervals[index...])
        return result
    }
}

Where the time goes, line by line

Variables: n = len(intervals) (the existing intervals; newInterval is a single interval).

Line	Per-call cost	Times executed	Contribution
L4, L5 (phase 1 copy)	$O(1)$ each	up to n	$O(n)$
L6, L7 (phase 2 merge)	$O(1)$ each	up to n	$O(n)$
L8 (insert merged)	$O(1)$	1	$O(1)$
L9, L10 (phase 3 copy)	$O(1)$ each	up to n	$O(n)$ ← all phases together

No phase dominates; every interval is visited exactly once across the three phases. Total work is $O(n)$ with no sorting because the input is already sorted.

Complexity

• Time: $O(n)$, driven by the single pass across all three phases (L4-L10).
• Space: $O(n)$.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Append + re-merge	$O(n log n)$	$O(n)$
Binary search + local merge	$O(n)$	$O(n)$
Single-pass three-phase	$O(n)$	$O(n)$

The three-phase template is the cleanest answer.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_057_insert_interval.py and run.
# Uses the canonical implementation (Approach 3).

def insert(intervals, new_interval):
    result = []
    i = 0
    n = len(intervals)

    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval = [min(new_interval[0], intervals[i][0]),
                        max(new_interval[1], intervals[i][1])]
        i += 1
    result.append(new_interval)

    while i < n:
        result.append(intervals[i])
        i += 1

    return result

def _run_tests():
    # Example 1 from problem statement
    assert insert([[1,3],[6,9]], [2,5]) == [[1,5],[6,9]]
    # Example 2: spans multiple intervals
    assert insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]) == [[1,2],[3,10],[12,16]]
    # Insert at the start (no overlap)
    assert insert([[3,5],[6,9]], [1,2]) == [[1,2],[3,5],[6,9]]
    # Insert at the end (no overlap)
    assert insert([[1,2],[3,5]], [7,9]) == [[1,2],[3,5],[7,9]]
    # Completely subsumes all existing intervals
    assert insert([[1,2],[3,4],[5,6]], [0,10]) == [[0,10]]
    # Empty intervals list
    assert insert([], [1,5]) == [[1,5]]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function insert(intervals: number[][], newInterval: number[]): number[][] {
    const result: number[][] = [];
    let i = 0;
    const n = intervals.length;
    while (i < n && intervals[i][1] < newInterval[0]) { result.push([...intervals[i]]); i++; }
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval = [Math.min(newInterval[0], intervals[i][0]), Math.max(newInterval[1], intervals[i][1])];
        i++;
    }
    result.push(newInterval);
    while (i < n) { result.push([...intervals[i]]); i++; }
    return result;
}

console.assert(JSON.stringify(insert([[1,3],[6,9]], [2,5])) === JSON.stringify([[1,5],[6,9]]));
console.assert(JSON.stringify(insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])) === JSON.stringify([[1,2],[3,10],[12,16]]));
console.assert(JSON.stringify(insert([[3,5],[6,9]], [1,2])) === JSON.stringify([[1,2],[3,5],[6,9]]));
console.assert(JSON.stringify(insert([[1,2],[3,5]], [7,9])) === JSON.stringify([[1,2],[3,5],[7,9]]));
console.assert(JSON.stringify(insert([[1,2],[3,4],[5,6]], [0,10])) === JSON.stringify([[0,10]]));
console.assert(JSON.stringify(insert([], [1,5])) === JSON.stringify([[1,5]]));
console.log("all tests pass");

Related data structures

• Arrays, sorted list of intervals; in-place walk

Related concepts

• Intervals, range-boundary tactics for overlap, containment, scheduling, and sweep-line problems.
• Merge Intervals, sorted-boundary tactics for combining overlapping ranges and maintaining the current covered span.