Insert Interval

One pass: before, merge, after

time O(n)space O(n)

Because the input list is already sorted and non-overlapping, a new interval can only ever collide with a contiguous run of existing ones — never scattered ones. So one linear pass does it: copy every interval that ends before the new one starts untouched, absorb every interval that overlaps into a single growing merged interval, then copy whatever's left.

Details

Animated on: intervals = [[1,3],[6,9]], newInterval = [2,5] — insert and merge, keeping the list sorted and disjoint.

Problem:Insert IntervalMedium

Pattern:Intervals

One pass: before, merge, after

step 1 / 4

[1,3]

[0]

[6,9]

[1]

intervals=[1,3],[6,9], inserting [2,5]. Since intervals arrive sorted by start, we only need one pass.

Pseudocode

1FUNCTION insert(intervals, newInterval):
2  result = empty list
3  WHILE the end of intervals[i] < the start of newInterval:
4    append intervals[i] to result; move i one step right   (no overlap yet)
5  WHILE the start of intervals[i] <= the end of newInterval:
6    newInterval = merge of newInterval and intervals[i]; move i one step right
7  append newInterval to result
8  WHILE i < n: append intervals[i] to result; move i one step right

← / → step · space play · Home restart

Every step in words

Show all 4 steps

intervals=[1,3],[6,9], inserting [2,5]. Since intervals arrive sorted by start, we only need one pass.
[1,3] overlaps [2,5] (start 1 <= end 5). Merge: [min(2,1), max(5,3)] = [1,5].
No more overlaps — insert the fully-merged interval [1,5] into the result.
Append any remaining untouched intervals. Final result: [1,5], [6,9].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Insert Interval in the editor All Intervals problems Back to roadmap