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.
In this approach, we'll first identify where the new interval should be inserted to maintain order. After insertion, we'll iterate over the array and merge overlapping intervals.
The C solution allocates memory for a new set of intervals that can hold the original intervals plus the new one. It adds all the intervals that end before the new interval's start. Next, it merges overlapping intervals with the new interval. Finally, all remaining intervals are appended after the merged intervals. The function returns the new list of intervals.
Time Complexity: O(n), where n is the number of intervals.
Space Complexity: O(n) due to the allocation for the result.
This approach optimizes finding the insert position using binary search. After inserting the new interval, it merges overlapping intervals. This is slightly more efficient when the intervals list is large.
This C solution integrates binary search to locate the accurate insertion index for the new interval before merging. Although binary search optimizes finding the position, the merge process remains linear.
Time Complexity: O(n), even with binary search (O(log n) for insertion, O(n) for merging).
Space Complexity: O(n), to store the new list of intervals.
| Approach | Complexity |
|---|---|
| Approach 1: Insert and Merge Intervals | Time Complexity: O(n), where n is the number of intervals. |
| Approach 2: Binary Search for Insert Position then Merge | Time Complexity: O(n), even with binary search (O(log n) for insertion, O(n) for merging). |
| 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 |
Insert Interval - Leetcode 57 - Python • NeetCode • 230,450 views views
Watch 9 more video solutions →Practice Insert Interval with our built-in code editor and test cases.
Practice on FleetCode