Insert Interval
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.](https://storage.ghost.io/c/cc/3d/cc3dd2ec-1125-4515-87dd-11389c0d3c50/content/images/2026/11/000-71ffb1d5.png)
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
- Are the existing intervals sorted and non-overlapping? (Here: yes; that's what makes O(n) possible.)
- Do touching intervals merge? (Here: yes, closed intervals.)
- Can I return a new list, or must I modify in place? (Here: a new list.)
- Can the input list be empty? (Yes; the answer is just the new interval.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.