Insert Interval
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves adding the new interval to the existing list of intervals and then treating it as a standard 'Merge Intervals' problem. The combined list is first sorted by the start times of the intervals, and then a linear scan is performed to merge any overlapping intervals.
Algorithm
- Create a new
List<int[]>. - Add all intervals from the input
intervalsarray to the list. - Add
newIntervalto the list. - Sort the list based on the start time of the intervals using a custom comparator.
- Initialize an empty
mergedlist to store the final result. - If the combined list is not empty, add the first interval to the
mergedlist. - Iterate through the sorted list from the second interval.
- For each interval, check if it overlaps with the last interval in the
mergedlist (i.e.,current.start <= lastMerged.end). - If it overlaps, update the end of the last interval in
mergedto be the maximum of the two end times:lastMerged.end = max(lastMerged.end, current.end). - If it does not overlap, add the current interval to the
mergedlist. - Convert the
mergedlist to a 2D array and return it.
Walkthrough
The core idea is to simplify the problem by leveraging a known algorithm for merging intervals. First, we create a new list that contains all the intervals from the input intervals array plus the newInterval. This combined list is not guaranteed to be sorted or non-overlapping. We then sort this list based on the starting point of each interval. After sorting, we can iterate through the list and merge intervals. We initialize a result list with the first interval. Then, for each subsequent interval, we check if it overlaps with the last interval in our result list. If it overlaps, we merge them by updating the end point of the last interval in the result list. If it doesn't overlap, we simply add the current interval to the result list. Finally, we convert the result list back to a 2D array.
import java.util.ArrayList;import java.util.Arrays;import java.util.Comparator;import java.util.List; class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> allIntervals = new ArrayList<>(Arrays.asList(intervals)); allIntervals.add(newInterval); // Sort the combined list by the start of each interval allIntervals.sort(Comparator.comparingInt(a -> a[0])); List<int[]> merged = new ArrayList<>(); if (allIntervals.isEmpty()) { return new int[0][]; } merged.add(allIntervals.get(0)); for (int i = 1; i < allIntervals.size(); i++) { int[] current = allIntervals.get(i); int[] lastMerged = merged.get(merged.size() - 1); // Check for overlap if (current[0] <= lastMerged[1]) { // Merge by updating the end of the last merged interval lastMerged[1] = Math.max(lastMerged[1], current[1]); } else { // No overlap, add the current interval merged.add(current); } } return merged.toArray(new int[merged.size()][]); }}Complexity
Time
O(N log N), where N is the number of intervals. The sorting step dominates the time complexity.
Space
O(N), for storing the combined list of intervals and the final merged list, where N is the number of intervals in the input.
Trade-offs
Pros
Conceptually simple, as it reduces the problem to a well-known one ('Merge Intervals').
Easy to implement if you already have a solution for merging intervals.
Cons
Inefficient because it doesn't utilize the pre-sorted nature of the input
intervalsarray.The sorting step
O(N log N)is the bottleneck and is an unnecessary overhead.
A more efficient approach is to iterate through the sorted intervals array just once, taking advantage of its sorted property. We can build the result list by handling three distinct cases in a single pass: intervals that come before the new interval, intervals that overlap with it, and intervals that come after it.
Algorithm
- Initialize an empty
resultlist and an indexi = 0. - Phase 1: Add non-overlapping intervals from the beginning. Iterate through
intervalswhile the current interval's end is less thannewInterval's start (intervals[i][1] < newInterval[0]). Add these intervals toresult. - Phase 2: Merge overlapping intervals. Iterate through
intervalswhile the current interval's start is less than or equal tonewInterval's end (intervals[i][0] <= newInterval[1]). In each step, merge the current interval intonewIntervalby updatingnewInterval's start and end:newInterval[0] = min(newInterval[0], intervals[i][0])andnewInterval[1] = max(newInterval[1], intervals[i][1]). - After the merging loop, add the final, merged
newIntervalto theresultlist. - Phase 3: Add remaining intervals. Add all remaining intervals from the input array (from the current position of
ito the end) to theresultlist. - Convert the
resultlist to a 2D array and return it.
Walkthrough
This approach avoids re-sorting and processes the intervals in a single linear scan. We iterate through the intervals and divide the process into three parts.
Part 1: Add non-overlapping intervals from the beginning. We iterate through the intervals array and add all intervals that end before newInterval starts to our result list. These intervals are guaranteed not to overlap with newInterval or any subsequent intervals.
Part 2: Merge overlapping intervals. We continue iterating through the intervals array. For all intervals that overlap with newInterval (i.e., their start is less than or equal to newInterval's end), we merge them into newInterval. This is done by repeatedly updating newInterval's start to the minimum of the current starts and its end to the maximum of the current ends.
Part 3: Add the merged interval and remaining intervals. After the merging loop, the newInterval now represents the combination of the original newInterval and all intervals it overlapped with. We add this merged newInterval to the result list. Then, we add all the remaining intervals from the input array to the result list. These are guaranteed to start after the merged newInterval ends.
Finally, we convert the result list to a 2D array.
import java.util.ArrayList;import java.util.List; class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> result = new ArrayList<>(); int i = 0; int n = intervals.length; // 1. Add all intervals that end before newInterval starts while (i < n && intervals[i][1] < newInterval[0]) { result.add(intervals[i]); i++; } // 2. Merge all overlapping intervals with newInterval while (i < n && intervals[i][0] <= newInterval[1]) { newInterval[0] = Math.min(newInterval[0], intervals[i][0]); newInterval[1] = Math.max(newInterval[1], intervals[i][1]); i++; } // Add the merged interval result.add(newInterval); // 3. Add all remaining intervals while (i < n) { result.add(intervals[i]); i++; } return result.toArray(new int[result.size()][]); }}Complexity
Time
O(N), where N is the number of intervals, as we iterate through the list only once.
Space
O(N), for storing the result list. In the worst case, the result has N+1 intervals.
Trade-offs
Pros
Highly efficient with a linear time complexity.
Effectively uses the pre-sorted property of the input array, avoiding a costly re-sort.
Requires only a single pass through the data.
Cons
The logic is slightly more complex than the brute-force approach, involving multiple conditions and loops to handle the three distinct phases.
Solutions
Solution
public class Solution { public int[][] Insert(int[][] intervals, int[] newInterval) { var ans = new List < int[] > (); int st = newInterval[0], ed = newInterval[1]; bool insert = false; foreach(var interval in intervals) { int s = interval[0], e = interval[1]; if (ed < s) { if (!insert) { ans.Add(new int[] { st, ed }); insert = true; } ans.Add(interval); } else if (st > e) { ans.Add(interval); } else { st = Math.Min(st, s); ed = Math.Max(ed, e); } } if (!insert) { ans.Add(new int[] { st, ed }); } return ans.ToArray(); }}class Solution {public int[][] insert(int[][] intervals, int[] newInterval) { int[][] newIntervals = new int[intervals.length + 1][2]; for (int i = 0; i < intervals.length; ++i) { newIntervals[i] = intervals[i]; } newIntervals[intervals.length] = newInterval; return merge(newIntervals); }private int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a, b)->a[0] - b[0]); List<int[]> ans = new ArrayList<>(); ans.add(intervals[0]); for (int i = 1; i < intervals.length; ++i) { int s = intervals[i][0], e = intervals[i][1]; if (ans.get(ans.size() - 1)[1] < s) { ans.add(intervals[i]); } else { ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], e); } } return ans.toArray(new int[ans.size()][]); }}class Solution {public: vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval) { intervals.emplace_back(newInterval); return merge(intervals); } vector<vector<int>> merge(vector<vector<int>> &intervals) { sort(intervals.begin(), intervals.end()); vector<vector<int>> ans; ans.emplace_back(intervals[0]); for (int i = 1; i < intervals.size(); ++i) { if (ans.back()[1] < intervals[i][0]) { ans.emplace_back(intervals[i]); } else { ans.back()[1] = max(ans.back()[1], intervals[i][1]); } } return ans; }};''' >>> a = [1,2,3,4,5] >>> a[1] 2 >>> a[~1] 4 ''' class Solution : def insert ( self , intervals : List [ List [ int ]], newInterval : List [ int ]) -> List [ List [ int ]]: start = newInterval [ 0 ] end = newInterval [ 1 ] left = list ( filter ( lambda x : x [ 1 ] < start , intervals )) # cast via list() right = list ( filter ( lambda x : x [ 0 ] > end , intervals )) if left + right != intervals : start = min ( start , intervals [ len ( left )][ 0 ]) # note, left not -1, because index starts at 0 end = max ( end , intervals [ ~ len ( right )][ 1 ]) # same, starting at right with index=0 return left + [[ start , end ]] + right ###### class Solution : # re-use Leetcode-56's merge solution def insert ( self , intervals : List [ List [ int ]], newInterval : List [ int ]) -> List [ List [ int ]]: intervals . append ( newInterval ) return self . merge ( intervals ) def merge ( self , intervals : List [ List [ int ]]) -> List [ List [ int ]]: ans = [] for intv in sorted ( intervals , key = lambda x : x [ 0 ]): if ans and ans [ - 1 ][ 1 ] >= intv [ 0 ]: ans [ - 1 ][ 1 ] = max ( ans [ - 1 ][ 1 ], intv [ 1 ]) else : ans . append ( intv ) return ans ###### class Solution : def insert ( self , intervals : List [ List [ int ]], newInterval : List [ int ] ) -> List [ List [ int ]]: def merge ( intervals : List [ List [ int ]]) -> List [ List [ int ]]: intervals . sort () ans = [ intervals [ 0 ]] for s , e in intervals [ 1 :]: if ans [ - 1 ][ 1 ] < s : ans . append ([ s , e ]) else : ans [ - 1 ][ 1 ] = max ( ans [ - 1 ][ 1 ], e ) return ans intervals . append ( newInterval ) return merge ( intervals )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.