Insert Interval

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    You have a list of non-overlapping intervals sorted by start, and one new interval. Insert the new interval so the list stays sorted and non-overlapping, merging wherever it overlaps, and return the result. Intervals are closed: [1, 3] and [3, 5] overlap.

    It's the "already sorted" cousin of Merge Intervals. Because the input is sorted you can skip the sort and finish in one linear pass, as long as you split the walk into the right three phases. Original problem: LeetCode 57.

    Example

    The new interval [4, 9] touches [3, 5], [6, 7] and [8, 10], which all merge into [3, 10]; [1, 2] and [12, 16] stay as they are.
    The new interval [4, 9] touches [3, 5], [6, 7] and [8, 10], which all merge into [3, 10]; [1, 2] and [12, 16] stay as they are.
    Input:  intervals = [[1,2], [3,5], [6,7], [8,10], [12,16]], new = [4,9]
    Output: [[1,2], [3,10], [12,16]]
    Input:  intervals = [[1,5]], new = [2,3]
    Output: [[1,5]]          # fully inside an existing interval

    Constraints (assumed)

    • 0 ≤ n ≤ 10,000; intervals sorted by start and non-overlapping.
    • 0 ≤ start ≤ end ≤ 10⁵.

    What this question tests

    • Using a sorted input instead of re-sorting.
    • Splitting a scan into clear phases with exact boundary conditions.
    • The same overlap test as Merge Intervals, applied to a single moving interval.

    Questions to ask first

    1. Are the existing intervals sorted and non-overlapping? (Here: yes; that's what makes O(n) possible.)
    2. Do touching intervals merge? (Here: yes, closed intervals.)
    3. Can I return a new list, or must I modify in place? (Here: a new list.)
    4. Can the input list be empty? (Yes; the answer is just the new interval.)