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 <= 105The key idea in Insert Interval is to maintain the sorted, non-overlapping structure of the existing intervals while correctly placing the new interval. Because the intervals are already sorted by start time, you can process them in a single linear pass.
First, add all intervals that end before the new interval starts since they cannot overlap. Next, handle the overlapping section by merging intervals. During this phase, update the start and end of the new interval using min(start) and max(end) across overlaps. Finally, once merging is complete, insert the merged interval and append the remaining intervals that start after it.
This approach works efficiently because each interval is processed only once. The overall time complexity is O(n), where n is the number of intervals, and the extra space is mainly for storing the resulting list of intervals.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Linear Scan with Interval Merging | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Intervals Array is sorted. Can you use Binary Search to find the correct position to insert the new Interval.?
Can you try merging the overlapping intervals while inserting the new interval?
This can be done by comparing the end of the last interval with the start of the new interval and vice versa.
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.
Time Complexity: O(n), where n is the number of intervals.
Space Complexity: O(n) due to the allocation for the result.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct Interval {
5 int start;
6 int end;
7};
8
9struct Interval* insert(struct Interval* intervals, int intervalsSize, struct Interval newInterval, int* returnSize) {
10 struct Interval* result = malloc(sizeof(struct Interval) * (intervalsSize + 1));
11 int i, j = 0;
12 for (i = 0; i < intervalsSize && intervals[i].end < newInterval.start; ++i) {
13 result[j++] = intervals[i];
14 }
15 for (; i < intervalsSize && intervals[i].start <= newInterval.end; ++i) {
16 newInterval.start = fmin(newInterval.start, intervals[i].start);
17 newInterval.end = fmax(newInterval.end, intervals[i].end);
18 }
19 result[j++] = newInterval;
20 while (i < intervalsSize) {
21 result[j++] = intervals[i++];
22 }
23 *returnSize = j;
24 return result;
25}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.
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.
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.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Insert Interval is a common interview problem at companies like Google, Amazon, and Meta. It tests your understanding of interval merging, array traversal, and edge case handling in algorithm design.
The optimal approach is a linear scan through the sorted intervals. You first add non-overlapping intervals before the new interval, then merge overlapping intervals, and finally append the remaining intervals. This ensures the list stays sorted and non-overlapping in O(n) time.
A dynamic array or list is typically sufficient for this problem. Since intervals are already sorted, you can iterate once and build a result list while merging overlaps, making arrays an efficient and simple choice.
Merge Intervals requires merging overlaps in an entire list of intervals, usually after sorting. Insert Interval assumes the list is already sorted and non-overlapping, and the task is to insert a new interval while preserving that property.
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.