Insert Interval

1Medium

Insert Interval

Given non-overlapping sorted intervals and a new interval, insert the new interval and merge if necessary. Return the resulting intervals.

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]]

Jnaneshwara Reddy Satti

Builder · ClearCode

Hi — I'm a 21yo CS grad from India. I built ClearCode while recovering from a surgery, because I genuinely believe DSA should be visual, free, and accessible to everyone. No VC funding. No team. Just me, my laptop, and a lot of chai. ☕

If ClearCode helped you understand even one concept — consider supporting it. Every rupee keeps the servers running and new videos coming.

Support via Razorpay

Found this helpful? Support ClearCode ☕ — keeps it free forever

Algorithm Visualizer

O(N)

Before starting this video, please check the description to ensure you know the prerequisites. If you're comfortable with arrays and hash maps, let's go!

TEST CASE: []O(N)

clearcode.in

Execution Trace

1def insert(intervals, newInterval):

2 result = []

3 i = 0

4 while i < len(intervals) and intervals[i][1] < newInterval[0]:

5 result.append(intervals[i])

6 i += 1

7 while i < len(intervals) and intervals[i][0] <= newInterval[1]:

8 newInterval[0] = min(newInterval[0], intervals[i][0])

9 newInterval[1] = max(newInterval[1], intervals[i][1])

10 i += 1

11 result.append(newInterval)

12 while i < len(intervals):

13 result.append(intervals[i])

14 i += 1

15 return result

0:00 / 6:54