Watch 10 video solutions for Insert Interval, a medium level problem involving Array. This walkthrough by NeetCode has 186,576 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Note that you don't need to modify intervals in-place. You can make a new array and return it.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Constraints:
0 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 105intervals is sorted by starti in ascending order.newInterval.length == 20 <= start <= end <= 105Problem Overview: You’re given a list of non-overlapping intervals sorted by start time. Insert a new interval into the list and merge any overlaps so the final result remains sorted and non-overlapping.
Approach 1: Insert and Merge Intervals (O(n) time, O(n) space)
Iterate through the intervals and build the result list while handling three cases: intervals completely before the new interval, overlapping intervals, and intervals completely after it. First append all intervals whose end is smaller than newInterval[0]. Next merge overlaps by updating newInterval using start = min(start, interval[0]) and end = max(end, interval[1]). Once merging is complete, append the merged interval and then append the remaining intervals. This works because the input is already sorted, so overlapping intervals appear consecutively. Time complexity is O(n) since you scan the list once, and space complexity is O(n) for the output array. This is a classic pattern for interval problems built on simple iteration over an array.
Approach 2: Binary Search for Insert Position then Merge (O(n) time, O(1)-O(n) space)
Instead of scanning from the start, use binary search to find the first interval whose start time is greater than or equal to the new interval’s start. This gives the insertion position in O(log n). Insert the interval at that index, then perform a standard merge pass over the list to combine overlaps. The merge step still takes O(n), so the overall complexity remains O(n). This method is useful when you frequently insert intervals into a large sorted list because locating the insertion point becomes faster. It combines searching techniques from binary search with the standard interval merging pattern.
Recommended for interviews: The single-pass insert-and-merge approach is what interviewers expect. It shows that you recognize the sorted property and can merge intervals efficiently in one traversal. The binary search variant demonstrates deeper understanding of optimizing insertion, but the straightforward O(n) merge approach is usually considered the cleanest and most practical solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Insert and Merge Intervals | O(n) | O(n) | Standard interview solution when intervals are already sorted and non-overlapping |
| Binary Search Insert then Merge | O(n) | O(1)-O(n) | Useful when repeatedly inserting into a large sorted interval list and you want faster index lookup |