Insert Interval - Solution & Explanation
Problem Statement
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 <= 105intervalsis sorted bystartiin ascending order.newInterval.length == 20 <= start <= end <= 105
Approach Overview
Problem 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 1: Approach 1: Insert and Merge Intervals
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.
Complexity
Time Complexity: O(n), where n is the number of intervals.
Space Complexity: O(n) due to the allocation for the result.
Approach 2: Approach 2: Binary Search for Insert Position then Merge
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.
Complexity
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 3: Sorting + Interval Merging
We can first add the new interval newInterval to the interval list intervals, and then merge according to the regular method of interval merging.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of intervals.
Approach 4: One-pass Traversal
We can traverse the interval list intervals, let the current interval be interval, and there are three situations for each interval:
- The current interval is on the right side of the new interval, that is,
newInterval[1] < interval[0]. At this time, if the new interval has not been added, then add the new interval to the answer, and then add the current interval to the answer. - The current interval is on the left side of the new interval, that is,
interval[1] < newInterval[0]. At this time, add the current interval to the answer. - Otherwise, it means that the current interval and the new interval intersect. We take the minimum of the left endpoint of the current interval and the left endpoint of the new interval, and the maximum of the right endpoint of the current interval and the right endpoint of the new interval, as the left and right endpoints of the new interval, and then continue to traverse the interval list.
After the traversal, if the new interval has not been added, then add the new interval to the answer.
The time complexity is O(n), where n is the number of intervals. Ignoring the space consumption of the answer array, the space complexity is O(1).
Complexity Comparison
| 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). |
| Sorting + Interval Merging | — |
| One-pass Traversal | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Insert Interval - Leetcode 57 - Python • NeetCode • 241,282 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Insert Interval easy or hard?
How to solve Insert Interval in O(n)?
What is the best approach for Insert Interval?
Is Insert Interval asked at Google/Amazon/Meta?
What data structure is used in Insert Interval?
What is the time complexity of Insert Interval?
Insert Interval Python or Java solution approach?
Ready to solve this problem?
Practice Insert Interval with our built-in code editor and test cases.
Practice on FleetCode