57. Insert Interval

MediumIntervals and Sweep LineLinear scan on sorted intervalsThree-phase interval splice

Insert Interval

You are given a set of non-overlapping intervals sorted by start, and a new interval. Insert the new interval so the result is still sorted and non-overlapping, merging with any intervals it overlaps.

Open official problem prompt ↗

In plain English

Splice one new range into an already-sorted, non-overlapping list while keeping both properties, merging where it touches existing ranges.

Picture it like this

Like booking a new time block on a tidy calendar: appointments that end before it stay put, ones it collides with get folded into a single longer block, and later ones shift right unchanged.

Example

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Why: [2,5] overlaps [1,3] (2 <= 3) and merges into [1,5]; [6,9] starts after 5 so it stays separate.

Constraints

0 <= intervals.length <= 10^4intervals[i].length == 20 <= start_i <= end_i <= 10^5intervals is sorted by start_i in ascending ordernewInterval.length == 20 <= start <= end <= 10^5

Pattern lesson

See the pattern, then code

Three-phase interval splice

↗

Intervals and Sweep Line

Meetings, schedules, overlapping ranges, resource allocation, or timeline events.. Because the list is already sorted, all intervals ending before the new one come first untouched, all intervals overlapping the new one form one merged block, and everything after is copied verbatim.

New words, made simpleKnow these before the algorithm

Non-overlapping: No two intervals share any point; each ends strictly before the next begins.
Splice: Insert an element into the correct position of an ordered sequence.
Overlap window: The contiguous run of existing intervals the new interval touches.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Append then re-run Merge Intervals

Correct but wastes the fact the list is already sorted.

Push newInterval onto the list, sort, and merge as in problem 56.

Time O(n log n)Space O(n)

Best choiceThree-phase linear splice

Exploits the pre-sorted order to finish in a single pass.

Copy intervals before, merge the overlapping run into newInterval, copy intervals after.

Time O(n)Space O(n)

The rule we keep true

Invariant

At any moment res holds a sorted, non-overlapping prefix of the answer, and every interval already processed is either fully before newInterval or fully absorbed into it.

Why this is correct

Reasoning

The sorted order partitions intervals into three contiguous zones relative to newInterval: strictly-before (end < new start), overlapping (start <= new end), and strictly-after. Handling each zone in order reproduces exactly the merged, sorted result.

The algorithm in three movesSay these aloud before coding

1Copy every interval that ends before newInterval starts

[1,3] ends 3 >= 2 -> overlaps

2While intervals overlap newInterval, expand newInterval to cover their union

new grows to [1,5]

3Append the merged newInterval

res = [[1,5],[6,9]]

4Copy every remaining interval unchanged

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[1,3]0

[2,5]1

[6,9]2

1 · Read[1,3]

2 · AskIs end 3 < new start 2?

3 · Update stateres = []

4 · Resultno, 3 >= 2 -> stop before-phase

Key takeaway

The new interval [2,5] absorbs [1,3] into [1,5]; [6,9] is untouched.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5-7Before phase
Copy intervals that end before the new interval starts; they cannot overlap.
2
Lines 8-11Overlap phase
Expand newInterval to the union of every interval it touches.
3
Lines 12Place merged interval
Insert the fully-grown newInterval at its correct sorted position.
4
Lines 13-15After phase
Copy the remaining intervals verbatim; they start after the new interval ends.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty intervals list — just return [newInterval]
newInterval before all existing intervals
newInterval after all existing intervals
newInterval that swallows several intervals at once
newInterval touching an existing endpoint exactly

Common beginner mistakes

Using < instead of <= in the overlap test and failing to merge touching intervals
Mutating newInterval but forgetting to append it
Off-by-one in the before-phase condition (comparing start instead of end)

Check your understanding

Why can the 'after' phase copy the rest without any further merging?

PyPython 3 · solution.py

Optimal

1class Solution:2    def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:3        res: list[list[int]] = []4        i, n = 0, len(intervals)5        while i < n and intervals[i][1] < newInterval[0]:6            res.append(intervals[i])7            i += 18        while i < n and intervals[i][0] <= newInterval[1]:9            newInterval[0] = min(newInterval[0], intervals[i][0])10            newInterval[1] = max(newInterval[1], intervals[i][1])11            i += 112        res.append(newInterval)13        while i < n:14            res.append(intervals[i])15            i += 116        return res

Time complexityO(n)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

GoogleMetaAmazonLinkedIn

Insert Interval

Insert Interval

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Intervals and Sweep Line