Given a sorted array of non-overlapping intervals where intervals[i] = [start_i, end_i], and a new interval newInterval = [start, end], insert the new interval into the list so that it remains sorted and non-overlapping. Merge any overlapping intervals if necessary, and return the updated list.
Example
intervals = [[1,3], [6,9]], newInterval = [2,5]
Output: [[1,5], [6,9]]
The new interval [2,5] overlaps with [1,3] (since 2 falls within 1-3), so they merge into [1,5]. The interval [6,9] does not overlap and stays unchanged.
Walk through the sorted intervals in three phases. First, add all intervals that end before the new interval starts (no overlap). Then, merge all intervals that overlap with the new interval by extending its start and end. Finally, add whatever intervals remain after the merged region.
Why this works
Since the existing intervals are already sorted, you can process them in one pass with three distinct phases: intervals entirely before the new one, intervals overlapping with the new one (which get merged together), and intervals entirely after. This avoids re-sorting and handles all edge cases cleanly.
Step by step
- Add all intervals that end before the new interval starts — these have no overlap at all.
- Merge overlapping intervals — while the current interval’s start is within the new interval’s range, absorb it by extending the new interval’s boundaries.
- Add the merged interval — after all overlaps are consumed, insert the (possibly enlarged) new interval.
- Add remaining intervals — everything after the merged region is added as-is.
Time: O(n)
Space: O(n)
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int i = 0;
int n = intervals.length;
while (i < n && intervals[i][1] < newInterval[0]) { // phase 1: entirely before
result.add(intervals[i]);
i++;
}
while (i < n && intervals[i][0] <= newInterval[1]) { // phase 2: overlapping — merge
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.add(newInterval); // add the merged interval
while (i < n) { // phase 3: entirely after
result.add(intervals[i]);
i++;
}
return result.toArray(new int[result.size()][]);
}
}
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> result;
int i = 0;
int n = intervals.size();
while (i < n && intervals[i][1] < newInterval[0]) { // phase 1: entirely before
result.push_back(intervals[i]);
i++;
}
while (i < n && intervals[i][0] <= newInterval[1]) { // phase 2: overlapping — merge
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
i++;
}
result.push_back(newInterval); // add the merged interval
while (i < n) { // phase 3: entirely after
result.push_back(intervals[i]);
i++;
}
return result;
}
};
def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
result = []
i = 0
n = len(intervals)
while i < n and intervals[i][1] < newInterval[0]: # phase 1: entirely before new interval
result.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= newInterval[1]: # phase 2: overlapping — merge them
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval) # add the (possibly enlarged) merged interval
while i < n: # phase 3: entirely after new interval
result.append(intervals[i])
i += 1
return result