Insert Interval
Problem Description
You are given an array of non-overlapping intervals intervals where intervals[i] = [startᵢ, endᵢ] represent the start and the end of the ith interval and intervals is sorted in ascending order by startᵢ. 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 startᵢ 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]]
Explanation: Because the new interval [2,5] overlaps with [1,3].
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 <= 10⁴
- intervals[i].length == 2
- 0 <= startᵢ <= endᵢ <= 10⁵
- intervals is sorted by startᵢ in ascending order.
- newInterval.length == 2
- 0 <= start <= end <= 10⁵
Basic Approach to solve the problem
What comes to mind after understanding the problem?
Since we have a sorted array of intervals, our task is to merge the new interval into this array at the correct position.
But before we can merge, we first need to find the right place to insert the new interval.
How do we find its correct position?
It’s simple—because the array is already sorted, we just compare the starting point of each interval (intervals[i][0]) with the starting point of the newInterval. If the current interval's start is smaller, we keep going. But as soon as we find an interval with a greater start value, we insert the newInterval right there and continue with the rest of the array.
If we traverse all the intervals and still haven’t placed the new interval, it means it should be added at the end.
Once the new interval is in its correct place, we proceed to merge any overlapping intervals, adjusting the start and end points as needed.
If two intervals overlap, we merge them by adjusting the ending point of the smaller (earlier) interval.
For example, if Interval 1 is [start1, end1] and Interval 2 is [start2, end2], and they overlap (start2 <= end1), we merge them into a single interval: [start1, max(end1, end2)].
This works because the start of the merged interval remains the same (the smaller start), but the end becomes the maximum of the two intervals' end points (max(end1, end2)), ensuring that we cover both intervals fully. After that, we return the final merged result.
This way, we ensure the intervals remain sorted and properly merged.
Let's understand with visuals
Approach to Solve the Problem
Here’s a clearer approach to solve the problem:
- Start by creating a new array called allIntervals to hold the final result.
- Loop through the original list of intervals:
- For each interval, compare it with the new interval.
- If the current interval comes before the new interval (meaning its start time is smaller), add it to allIntervals.
- Once you find the right place for the new interval (when the current interval’s start is greater), insert the new interval into allIntervals.
- If you’ve finished the loop and haven’t inserted the new interval yet (meaning it belongs at the end), add the new interval to allIntervals at the end.
- After placing the new interval, continue adding the rest of the intervals to allIntervals.
- Next, merge any overlapping intervals:
- Check if any of the intervals in allIntervals overlap with each other, and if they do, merge them by adjusting their start and end times accordingly.
- Finally, return the merged intervals in allIntervals as the result.
This approach ensures that the new interval is inserted at the correct position and any overlapping intervals are merged properly.
Let's understand with an example:
Let's do a concise dry run of the example, where intervals = [[1,3], [6,9]] and newInterval = [2,5].
Step-by-step Dry Run:
- Initialize allIntervals = [].
- Iterate over intervals:
- First, compare the interval [1,3] with newInterval [2,5].
- Since 1 <= 2, place [1,3] in allIntervals.
- Now, allIntervals = [[1, 3]].
- Now, compare [6,9] with newInterval [2,5].
- Since 6 > 5, the new interval should be inserted here. So, insert [2, 5] at this point.
- Now, allIntervals = [[1, 3], [2, 5]].
- Now, add the rest of intervals, [6,9]
- allIntervals = [[1, 3], [2, 5], [6, 9]].
- Now merge overlapping intervals:
- [1, 3] and [2, 5] overlap, so merge them: start = 1, end = max(3, 5) = 5.
- Now, allIntervals = [[1, 5]].
- [6, 9] does not overlap with [1, 5], so just add [6, 9].
- Now, allIntervals = [[1, 5], [6, 9]].
- Return the result: [[1, 5], [6, 9]].
Final Result: [[1, 5], [6, 9]]
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
// Step 1: Initialize a new vector to hold all intervals, including the new interval
vector<vector<int>> allIntervals;
// Step 2: Flag to track if newInterval has been placed
bool inserted = false;
// Step 3: Traverse through the existing intervals
for(int i = 0; i < intervals.size(); i++) {
// If the current interval starts after newInterval, place newInterval before it
if(intervals[i][0] > newInterval[0]) {
allIntervals.push_back(newInterval);
allIntervals.push_back(intervals[i]);
inserted = true;
} else {
// Otherwise, add the current interval to the result
allIntervals.push_back(intervals[i]);
}
}
// If newInterval wasn't inserted yet, place it at the end
if(!inserted) {
allIntervals.push_back(newInterval);
}
// Step 4: Now, merge overlapping intervals
vector<vector<int>> mergedIntervals;
mergedIntervals.push_back(allIntervals[0]);
// Step 5: Traverse through allIntervals and merge if necessary
for(int i = 1; i < allIntervals.size(); i++) {
// If the current interval overlaps with the last one in mergedIntervals
if(allIntervals[i][0] <= mergedIntervals.back()[1]) {
// Merge the intervals by updating the end time
mergedIntervals.back()[1] = max(mergedIntervals.back()[1], allIntervals[i][1]);
} else {
// If no overlap, simply add the current interval
mergedIntervals.push_back(allIntervals[i]);
}
}
// Step 6: Return the final list of merged intervals
return mergedIntervals;
}
};
2. Java Try on Compiler
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
// Step 1: Initialize a list to hold the result intervals
List<int[]> result = new ArrayList<>();
// Step 2: Flag to track if newInterval has been placed
boolean inserted = false;
// Step 3: Traverse through the existing intervals
for (int[] interval : intervals) {
// If the current interval starts after newInterval, place newInterval before it
if (interval[0] > newInterval[0]) {
if (!inserted) {
result.add(newInterval); // Insert newInterval before the current interval
inserted = true;
}
result.add(interval); // Add the current interval to the result
} else {
result.add(interval); // Otherwise, just add the current interval to the result
}
}
// If newInterval wasn't inserted yet, place it at the end
if (!inserted) {
result.add(newInterval);
}
// Step 4: Now, merge overlapping intervals
List<int[]> mergedIntervals = new ArrayList<>();
mergedIntervals.add(result.get(0)); // Add the first interval to the merged result
// Step 5: Traverse through allIntervals and merge if necessary
for (int i = 1; i < result.size(); i++) {
int[] last = mergedIntervals.get(mergedIntervals.size() - 1);
int[] current = result.get(i);
// If the current interval overlaps with the last one in mergedIntervals
if (current[0] <= last[1]) {
// Merge the intervals by updating the end time
last[1] = Math.max(last[1], current[1]);
} else {
// If no overlap, simply add the current interval
mergedIntervals.add(current);
}
}
// Step 6: Convert the result to an array and return it
return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
}
}
3. Python Try on Compiler
class Solution:
def insert(self, intervals, newInterval):
# Step 1: Initialize a new list to hold all intervals, including the new interval
all_intervals = []
# Step 2: Flag to track if newInterval has been placed
inserted = False
# Step 3: Traverse through the existing intervals
for interval in intervals:
# If the current interval starts after newInterval, place newInterval before it
if interval[0] > newInterval[0]:
all_intervals.append(newInterval)
all_intervals.append(interval)
inserted = True
else:
# Otherwise, add the current interval to the result
all_intervals.append(interval)
# If newInterval wasn't inserted yet, place it at the end
if not inserted:
all_intervals.append(newInterval)
# Step 4: Now, merge overlapping intervals
merged_intervals = [all_intervals[0]]
# Step 5: Traverse through allIntervals and merge if necessary
for interval in all_intervals[1:]:
# If the current interval overlaps with the last one in merged_intervals
if interval[0] <= merged_intervals[-1][1]:
# Merge the intervals by updating the end time
merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1])
else:
# If no overlap, simply add the current interval
merged_intervals.append(interval)
# Step 6: Return the final list of merged intervals
return merged_intervals
4. Javascript Try on Compiler
var insert = function(intervals, newInterval) {
// Step 1: Initialize a new array to hold all intervals, including the new interval
let allIntervals = [];
// Step 2: Flag to track if newInterval has been placed
let inserted = false;
// Step 3: Traverse through the existing intervals
for (let i = 0; i < intervals.length; i++) {
// If the current interval starts after newInterval, place newInterval before it
if (intervals[i][0] > newInterval[0]) {
allIntervals.push(newInterval);
allIntervals.push(intervals[i]);
inserted = true;
} else {
// Otherwise, add the current interval to the result
allIntervals.push(intervals[i]);
}
}
// If newInterval wasn't inserted yet, place it at the end
if (!inserted) {
allIntervals.push(newInterval);
}
// Step 4: Now, merge overlapping intervals
let mergedIntervals = [allIntervals[0]];
// Step 5: Traverse through allIntervals and merge if necessary
for (let i = 1; i < allIntervals.length; i++) {
// If the current interval overlaps with the last one in mergedIntervals
if (allIntervals[i][0] <= mergedIntervals[mergedIntervals.length - 1][1]) {
// Merge the intervals by updating the end time
mergedIntervals[mergedIntervals.length - 1][1] = Math.max(mergedIntervals[mergedIntervals.length - 1][1], allIntervals[i][1]);
} else {
// If no overlap, simply add the current interval
mergedIntervals.push(allIntervals[i]);
}
}
// Step 6: Return the final list of merged intervals
return mergedIntervals;
};
Time Complexity: O(n)
We iterate through the entire intervals array once to find the right position to insert the newInterval. In the worst case, we might have to traverse all n intervals. Thus, this step takes O(n) time.
After placing the newInterval in the correct position, we perform another traversal of the allIntervals (the list that contains newInterval and all other intervals). During this traversal, we check for overlapping intervals and merge them if necessary. Again, in the worst case, we iterate over all n intervals, and merging takes constant time (since merging only involves comparing and updating two values). So this step also takes O(n) time.
Overall Time Complexity: O(n) + O(n) = O(n), where n is the number of intervals in the original list.
Space Complexity: O(n)
- Auxiliary Space: O(n)
Explanation: We use a new array, allIntervals, to store all the intervals including the newInterval. In the worst case, this array can hold n + 1 intervals (where n is the number of original intervals), so the auxiliary space for this array is O(n).
We also use the mergedIntervals array, which again can hold up to n + 1 intervals in the worst case. Therefore, the auxiliary space for this array is also O(n). - Total Space Complexity: O(n)
Explanation: The total space complexity is the space used by the allIntervals and mergedIntervals arrays, which are both O(n) in the worst case.
Hence, the total space complexity is O(n).
Will Brute Force Work Against the Given Constraints?
For n ≤ 10 ⁴, our solution has a time complexity of O(N), which will comfortably meet the given constraints.
This is well within the time limits of most competitive programming environments, which typically allow around 1-2 seconds for execution.
In such environments, it is common for problems to handle up to 10⁶ operations within these limits.
Most competitive programming platforms, like LeetCode, allow up to 10⁶ operations per test case, meaning your solution should be able to handle this number of operations within the time limits. When multiple test cases are involved, the total number of operations can go up to 10⁸.
Thus, the O(N) time complexity is optimal and works efficiently even with large input sizes like n = 10 ⁴, ensuring the solution runs within the acceptable time frame without risking a Time Limit Exceeded (TLE) error.
Can there be another approach?
Yes, there is a more straightforward approach to solve this problem.
We can perform it in a single pass!
In the previous approach, we first placed the new interval at its correct position in the sorted list and then merged any overlapping intervals.
However, we can streamline this further by merging the intervals while placing the new interval at the same time. This eliminates the need for a separate merging step, making the solution more intuitive.
Here’s the plan:
- First, we go through the intervals and add them directly to the result if there's no overlap with the new interval.
How do we check this?
If the current interval ends before the new interval starts, they don't overlap. We can safely add these intervals to our result. - When we encounter overlapping intervals, we merge them by updating the start and end points of the new interval.
We'll update the new interval if it overlaps with the current interval. To do this, we set the start point of the new interval as the minimum of its own start point and the current interval's start point. Similarly, we'll update the end point of the new interval by taking the maximum of its own end point and the current interval's end point.
As long as they overlap, we continue updating the new interval's boundaries. - Finally, once we've merged all overlapping intervals, we continue adding any remaining intervals to the result that don’t overlap with the new interval.
This way, we’re handling both the placement and merging of the new interval in one pass, making the process much simpler and more efficient!
How can we do it?
Before we even think about merging, we need to check if the intervals before the new interval overlap with it. If not, we just add them to the result.
- As we traverse the intervals, we compare each interval's end with the start of the new interval.
- If the current interval’s end is less than the new interval’s start, it means the intervals come before the new interval and don’t overlap.
- So, we simply add these intervals to the result.
Once we encounter intervals that overlap with the new interval, we handle the merging.
- If the current interval’s start is less than or equal to the new interval’s end, we know that there is an overlap.
- We merge by updating the new interval’s start to be the minimum of the two starting points, and the new interval’s end to be the maximum of the two ending points.
- This way, the new interval expands to cover all overlapping intervals.
Once the new interval has been merged with any overlapping intervals, we add any remaining intervals that don’t overlap.
- These are simply intervals that come after the merged interval, and we can directly add them to the result without any further changes.
After handling all cases—intervals before, overlapping with, and after the new interval—we return the result.
In summary:
- We first place all non-overlapping intervals that come before the new interval.
- Then, we merge the new interval with any overlapping intervals.
- Finally, we add all remaining non-overlapping intervals after the new interval.
This approach is efficient because we handle the insertion and merging in a single pass through the intervals, ensuring optimal performance.
Let's understand with an example:
- Intervals: [[1,2], [3,5], [6,7], [8,10], [12,16]]
- New Interval: [4,8]
- Result: []
Step 1: No Overlap Before the New Interval
- Intervals[0] = [1,2]: Since 2 < 4, no overlap with the new interval.
- Add [1,2] to the result.
- Result = [[1,2]]
- Intervals[1] = [3,5]: 5 >= 4 (overlapping), so we stop adding and move to merging.
Step 2: Merge Overlapping Intervals
- [3,5] overlaps with [4,8]:
- Update the new interval:
- New Start = min(3, 4) = 3
- New End = max(5, 8) = 8
- Updated New Interval = [3,8]
- Intervals[2] = [6,7]: Overlaps with [3,8].
- Update again:
- New Start = min(3, 6) = 3
- New End = max(7, 8) = 8
- New Interval = [3,8]
- Intervals[3] = [8,10]: Overlaps with [3,8].
- Update again:
- New Start = min(3, 8) = 3
- New End = max(10, 8) = 10
- New Interval = [3,10]
- Now, push this merged interval to result.
- Result = [[1,2], [3,10]]
Step 3: No Overlap After Merging
- Intervals[4] = [12,16]: No overlap with [3,10].
- Add [12,16] to the result.
- Result = [[1,2], [3,10], [12,16]]
Final Result:
The final merged intervals are [[1,2], [3,10], [12,16]].
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int n = intervals.size(), i = 0;
vector<vector<int>> result;
// Step 1: Add intervals that come before the new interval (no overlap)
// We compare the end of the current interval with the start of the newInterval
while(i < n && intervals[i][1] < newInterval[0]){
result.push_back(intervals[i]);
i++;
}
// Step 2: Merge overlapping intervals
// As long as the start of the current interval is less than or equal to
// the end of the new interval, update the boundaries of newInterval
while(i < n && newInterval[1] >= intervals[i][0]){
newInterval[0] = min(newInterval[0], intervals[i][0]); // Update the start
newInterval[1] = max(newInterval[1], intervals[i][1]); // Update the end
i++;
}
// Add the merged interval to the result
result.push_back(newInterval);
// Step 3: Add remaining intervals (those that come after the merged newInterval)
while(i < n){
result.push_back(intervals[i]);
i++;
}
// Return the final merged result
return result;
}
};2. Java Try on Compiler
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int n = intervals.length, i = 0;
// Step 1: Add intervals that come before the new interval (no overlap)
while (i < n && intervals[i][1] < newInterval[0]) {
result.add(intervals[i]);
i++;
}
// Step 2: Merge overlapping intervals
while (i < n && newInterval[1] >= intervals[i][0]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.add(newInterval);
// Step 3: Add remaining intervals (those that come after the merged newInterval)
while (i < n) {
result.add(intervals[i]);
i++;
}
// Convert the result list to a 2D array and return
return result.toArray(new int[result.size()][]);
}
}3. Python Try on Compiler
class Solution(object):
def insert(self, intervals, newInterval):
"""
:type intervals: List[List[int]]
:type newInterval: List[int]
:rtype: List[List[int]]
"""
result = []
i, n = 0, len(intervals)
# Step 1: Add intervals that come before the new interval (no overlap)
while i < n and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
# Step 2: Merge overlapping intervals
while i < n and newInterval[1] >= intervals[i][0]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
# Step 3: Add remaining intervals (those that come after the merged newInterval)
while i < n:
result.append(intervals[i])
i += 1
return result4. Javascript Try on Compiler
var insert = function(intervals, newInterval) {
let result = [];
let i = 0, n = intervals.length;
// Step 1: Add intervals that come before the new interval (no overlap)
while (i < n && intervals[i][1] < newInterval[0]) {
result.push(intervals[i]);
i++;
}
// Step 2: Merge overlapping intervals
while (i < n && newInterval[1] >= intervals[i][0]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.push(newInterval);
// Step 3: Add remaining intervals (those that come after the merged newInterval)
while (i < n) {
result.push(intervals[i]);
i++;
}
return result;
};Time Complexity: O(n)
By combining all three loops into a single pass, we traverse the array in one go:
- First phase: Add non-overlapping intervals that end before the new interval starts to the result.
- Second phase: Merge overlapping intervals by adjusting the start and end of the new interval as needed.
- Third phase: Add the remaining non-overlapping intervals that come after the merged interval.
This approach ensures we only pass through the intervals once, making the time complexity O(n) and optimizing both time and space.
Space Complexity: O(n)
- Auxiliary Space: O(n)
Explanation: The only extra space used is the result array (result), which stores all the intervals, including the new merged interval. In the worst case, we might store all the n original intervals plus the new interval, leading to O(n) additional space. - Total Space Complexity: O(n)
Explanation: Apart from the input, we are only using an additional vector to store the result, making the total space complexity O(n).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Given an array of intervals where intervals[i] = [startᵢ, endᵢ], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
We are given an array [asteroids] of integers representing asteroids in a row.
For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.