Insert Interval

Difficulty: N/A | Solved: December 20, 2025

Problem

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]

Brainstorming

so the problem is a clever linear scan problem of arrays. lets get the requirements clear

we need to find non overlapping intervals before our new interval they should be part of our new interval range
we need to find non overlapping intervals after our new interval they also should be a part of our new interval range
for the interval that we find to overlap we need to merge them
1. we will take the min of the start value and the max of the end value that becomes a new interval that needs to be added

this is how the algorithm will look like

loop on the intervals array
1. for each interval in intervals check the end values of the interval and new interval if the end value of the new interval is more than the existing one it means they will overlap
  1. now we need to form a new interval that engulfs both the new and the old intervals , we do so my finding the min(star_interval, start_new_interval) and max(end_interval, end_new_interval)
  2. with this new interval formed we further our search for more overlapping intervals
in order to do step 1.2 we need to make sure that we compare all the new intervals with our newly formed interval. to do so we need to add another check if the interval we are checking is either present in the result or not and then check for the overlap

lets try to write it

intervals =[[1,3],[6,9]]
newInterval = [2,5]

# our results array
result = []

for interval in intervals:
	# we try to check if interval is already part of our result or not 
	if interval not in result or interval[1] <= new_interval[1]:
		merge_interval = [min(interval[0], new_interval[0]), max(interval[1],new_interval[1])]
		result.append(merge_interval)
	else:
		result.append(interval)

lets try to dry run the algo

intervals = [[1,3], [6,9]] new_interval = [2,5]

we iterate over intervals

[1,3] is it in our results array no , is interval[1] ie 3 less than or equal to new_interval[1] ie 6 yes its less
1. make a new interval with [1,3] and [2,5] using min and max of start and end intervals of both the overlapping intervals hence [1,5] make this part of our new results results = [[1,5]]
[6,9] we take this
1. is interval part of our results array No is interval[1] ie 9 less than or equal to newInterval[1] ie 5 No hence we we just add it as is to the results
  1. result = [[1,5],[6,9]]
we return the results array

the problem with the above algorithm is it will not be able to merge consecutive intervals

Let’s try a trickier example that will break the current code:
intervals = [[1,2], [3,5], [6,7], [8,10], [12,16]] newInterval = [4,8]

`The correct answer should be [[1,2], [3,10], [12,16]]. The newInterval [4,8] needs to merge with [3,5], then [6,7], and then [8,10] to form the final [3,10] block.

`Let’s dry run your algorithm with this:

interval = [1,2]: It doesn’t overlap with [4,8]. Let’s assume your code handles this and adds [1,2] to the result. result =[[1,2]]
interval = [3,5]: It overlaps with [4,8]. Your code correctly merges them into [min(3,4), max(5,8)] which is [3,8]. It adds this to the result. result = [[1,2], [3,8]]
interval = [6,7]: It overlaps with the original newInterval [4,8]. Your code merges them into [min(6,4), max(7,8)] which is [4,8]. It adds this. result =[[1,2], [3,8], [4,8]].
interval = [8,10]: It overlaps with the original newInterval [4,8]. Your code merges them into [min(8,4), max(10,8)] which is [4,10]. It adds this. result =[[1,2], [3,8], [4,8], [4,10]].

You can see the problem. The result is incorrect because you’re repeatedly merging with the original newInterval and adding intermediate results.

More robust approach Before merge After

The “BEFORE” Loop
First, create a loop that does one simple job: find all the intervals that are completely before the newInterval. An interval [s, e] is “before” if e < newInterval.start. Just add these directly to your result list.

The “MERGE” Loop
Now, start a second loop from where you left off. This loop’s job is to find all intervals that overlap. The condition for overlap is interval.start <= newInterval.end.

Crucially: Do NOT add anything to the result list here.
Just keep updating your newInterval by taking the min of the starts and the max of the ends.

# With newInterval = [4,8]
# Continue from [3,5]. Is 3 <= 8? Yes.
#   newInterval becomes [min(4,3), max(8,5)] -> [3,8]
# Next, [6,7]. Is 6 <= 8? Yes.
#   newInterval becomes [min(3,6), max(8,7)] -> [3,8]
# Next, [8,10]. Is 8 <= 8? Yes.
#   newInterval becomes [min(3,8), max(8,10)] -> [3,10]
# Next, [12,16]. Is 12 <= 10? No. Stop this loop.

The “AFTER” Stage
The MERGE loop is over. What is the very next thing you must do? You have your final, fully merged newInterval ([3,10]). Add it to the result list.

# result was [[1,2]]
# Add the final newInterval.
# result is now [[1,2], [3,10]]

intervals =[[1,2],[3,5],[6,7],[8,10],[12,16]]
new_interval = [2,5]
result = []
for interval in intervals:
	if interval[1] < new_interval[0]: # before
		result.append(new_interval)
	elif interval[0] <= new_interval[1]: # overlapping interval
		new_interval =  [min(interval[0], new_interval[0]), max(interval[1],new_interval[1])]
		result.append(new_interval)
	else: # after
		result.append(interval)

code is falling into the same subtle but critical trap: you are adding items to the result list too early.

An algorithm must handle all cases, including merging with multiple intervals. Let’s do a quick dry run with your new code to see why this is a problem.

Dry Run: The Flaw Revealed

intervals =[[1,2],[3,5],[6,7],[8,10],[12,16]] new_interval = [4,8] (A good, tricky example)
result = []

interval = [1,2]:
- interval[1] < new_interval[0] (i.e., 2 < 4) is TRUE.
- The if block runs.
- result.append(new_interval) is executed.
- result is now[[4,8]]. (Incorrect. We should have added [1,2]).

Let’s pause. We found a bug on the very first step. The “BEFORE” phase should add the current interval ([1,2]), not the new_interval.

The Core Insight: Delaying the Append

The problem is that you must finish all the merging before you add the result of the merge

Stage 1: The “BEFORE” stage.
- Create an empty result list.
- Go through the intervals. As long as they are all completely before new_interval, add them to result.
- Stop as soon as you find the first interval that is NOT completely before.
Stage 2: The “MERGE” stage.
- Now, continue from where you left off. As long as the intervals are overlapping with your (constantly updating) new_interval, do not add anything to result.
- Your only job in this stage is to keep updating new_interval by merging it with the current overlapping interval.
- Stop as soon as you find the first interval that does not overlap.
The CRITICAL step:
- The MERGE stage is over. NOW, and only now, do you add your final, fully-merged new_interval to the result list.
Stage 3: The “AFTER” stage.
- Continue from where you left off.
- Add all the remaining intervals, which are guaranteed to be “after” intervals, directly to the result list.

intervals =[[1,2],[3,5],[6,7],[8,10],[12,16]]
n = len(intervals)
new_interval = [2,5]
result = []

i = 0

# before
while intervals[i][1] < new_interval[0]:
	result.append(interval[i])
	i +=1

# merge
for j in range(i,n):
	if intervals[j][0] <= new_interval[1]:
		new_interval =  [min(interval[0], new_interval[0]), max(interval[1],new_interval[1])]
		i +=1
		
result.append(new_interval)

# after
while i < n:
	result.append(intervals[i])