Insert Interval
Problem Statement
You are given a sorted array of non-overlapping intervals and a single newInterval. Insert newInterval into the array so the result is still sorted by start and contains no overlapping intervals.
Input
An integer matrix intervals sorted by start with no overlaps, and an integer array newInterval = [start, end].
Output
An integer matrix after inserting and merging newInterval, still sorted and non-overlapping.
Constraints
- •
0 <= intervals.length <= 10^4 - •
intervals[i].length == 2 - •
newInterval.length == 2 - •
0 <= starti <= endi <= 10^5 - •
intervals is sorted by start and contains no overlaps
Examples
Example 1
intervals = [[1,3],[6,9]], newInterval = [2,5]
[[1,5],[6,9]]Example 2
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
[[1,2],[3,10],[12,16]]Learning Objectives
- Use the sorted, non-overlapping invariant to avoid re-sorting the input.
- Split the scan into before, overlap, and after phases.
- Merge the new interval by expanding both start and end boundaries.
- Handle endpoint-touching intervals with the correct closed-interval overlap rule.
Intuition
Pattern Recognition
The signal is insert one interval into a list that is already sorted and non-overlapping. The trap is treating this like Merge Intervals and sorting everything again. Sorting works, but it misses the stronger invariant and gives up the clean O(n) pass.
Because the old intervals are already disjoint and ordered, each interval falls into exactly one phase. It either ends before the new interval starts, overlaps the new interval, or starts after the merged new interval ends. Once you enter the after phase, no later interval can overlap because later starts are even larger.
Common mistakes
- ×Sorting the combined array and losing the intended O(n) use of the input invariant.
- ×Using **intervalEnd <= newStart** as the before condition, which fails when endpoints touch and should merge.
- ×Appending **newInterval** before all overlapping intervals have expanded it.
- ×Forgetting to copy the intervals after the merged interval is emitted.
Algorithm Explanation
Key idea
Use one linear scan with three phases. First copy every interval whose end is strictly before newInterval starts. Then merge every interval whose start is less than or equal to the current merged end. Finally append the merged interval and copy the remaining intervals.
Interval walkthrough
Use intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]] and newInterval = [4,8]. On the number line 1--2--3--4--5--6--7--8--9--10--12--16, [1,2] ends before 4, so it is copied unchanged. Carry the new interval [4,8]. The interval [3,5] overlaps it and pulls the carried start left to 3, giving [3,8]. Then [6,7] sits inside the carried interval, so it stays [3,8]. Then [8,10] touches at 8, so the carried interval extends to [3,10]. The next interval [12,16] starts after 10, so emit [3,10] and copy [12,16].
Algorithm
- Create an empty result list and start scanning from index 0.
- Copy intervals while intervalEnd < newStart because they are completely before the insertion.
- Initialise mergedStart and mergedEnd from newInterval.
- While the current interval starts at or before mergedEnd, merge it by taking the smaller start and larger end.
- Append the merged interval once the overlap phase ends.
- Copy all remaining intervals because they start after the merged interval.
- Return the result list as an int[][].
Solutions
Solution: Three-phase linear insertion
Use this when the input guarantee says intervals are already sorted and non-overlapping. It is simpler and faster than sorting the combined list.
Scan once. Copy intervals that are fully before newInterval, merge the consecutive block that overlaps it, then copy the intervals that are fully after it.
Step-by-step
- Create result and an index at the beginning of intervals.
- Add all intervals with end < newInterval[0] to result.
- Carry mergedStart and mergedEnd from newInterval.
- While intervals overlap the carried range, update both carried boundaries.
- Add the carried merged interval to result.
- Add every remaining interval unchanged and return the matrix.
O(n)
O(n)
Each existing interval is visited once. The output list can contain O(n) intervals.
Java implementation
Dry Run
Sample input
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8].
| phase | interval considered | merged interval before | action | result so far |
|---|---|---|---|---|
| before | [1,2] | [4,8] | 2 < 4, copy it | [[1,2]] |
| overlap | [3,5] | [4,8] | merge to [3,8] | [[1,2]] |
| overlap | [6,7] | [3,8] | stays [3,8] | [[1,2]] |
| overlap | [8,10] | [3,8] | touches at 8, merge to [3,10] | [[1,2]] |
| after | [12,16] | [3,10] | 12 > 10, emit merged then copy rest | [[1,2],[3,10],[12,16]] |
The old intervals are already ordered, so the overlapping block is contiguous. Once [12,16] starts after the carried end 10, the merge phase is over.
Interview Tips
Call out the three phases before coding: before, overlap, after. This prevents messy conditionals. The before condition is end < newStart, not end <= newStart, because closed intervals that touch should be merged.
Likely follow-ups
- What if multiple new intervals must be inserted at once?
- What if the existing intervals were not sorted or could already overlap?
- How would you insert intervals online and answer queries after each insertion?
- How would the conditions change for half-open intervals?
Similar Problems
Key Takeaways
- The sorted, non-overlapping input turns insertion into a single pass.
- Intervals before the new interval satisfy **end < newStart**.
- The overlap phase is contiguous, so merge all of it before appending the carried interval.
- After the merged interval is emitted, every remaining interval can be copied unchanged.