Insert Interval: Merge on the Fly

LeetCode 57, Insert Interval, asks you to take a sorted list of non-overlapping intervals and insert a new interval into the right place, merging any overlaps along the way. The input is already sorted and non-overlapping, so you do not need to sort first. The challenge is handling the merge cleanly in a single pass.

The problem

You are given an array of non-overlapping intervals intervals sorted by start time, and a new interval newInterval. Insert newInterval into intervals so that the result is still sorted and non-overlapping, merging where necessary.

Example: intervals = [[1,3],[6,9]], newInterval = [2,5] produces [[1,5],[6,9]].

The new interval [2,5] overlaps [1,3] because 2 falls inside [1,3]. They merge into [1,5]. The interval [6,9] does not overlap, so it stays unchanged.

The approach: three phases

Because the input is already sorted and non-overlapping, you can walk through the intervals left to right and split the work into three phases:

1. Before. Add all intervals that end before the new interval starts. These have no overlap with the new interval.
2. Merge. For every interval that overlaps the new interval, absorb it by expanding the new interval's start and end. When this phase finishes, add the (possibly expanded) new interval to the result.
3. After. Add all remaining intervals. They start after the merged interval ends.

Each interval is visited exactly once. No sorting needed because the input is already in order.

def insert(intervals, newInterval):
    result = []
    i = 0
    n = len(intervals)

    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1

    result.append(newInterval)

    while i < n:
        result.append(intervals[i])
        i += 1

    return result

Visual walkthrough

Let's trace through intervals = [[1,3],[6,9]] with newInterval = [2,5].

The first phase finds no intervals entirely before [2,5] because [1,3] ends at 3, which is not less than 2. In the second phase, [1,3] overlaps [2,5], so the new interval expands to [1,5]. Then [6,9] does not overlap [1,5] (6 is greater than 5), so the merge phase ends and [1,5] gets added to the result. The third phase appends [6,9] as-is.

The phase boundaries explained

The first while loop uses intervals[i][1] < newInterval[0]. This checks whether the current interval ends strictly before the new interval starts. If true, there is zero overlap, and the interval belongs in the "before" group.

The second while loop uses intervals[i][0] <= newInterval[1]. This checks whether the current interval starts at or before the new interval ends. Combined with the fact that the first loop already skipped all non-overlapping intervals on the left, this condition catches every interval that touches or overlaps the new interval.

Inside the merge loop, min and max expand the new interval to cover everything it touches. After the loop, the new interval represents the full merged range.

Complexity analysis

Time: O(n). Each interval is visited exactly once across the three while loops. There is no sorting step because the input is pre-sorted.

Space: O(n). The result list can hold up to n + 1 intervals (the original intervals plus the new one, if no merges happen).

This is optimal. You must read every interval at least once, so O(n) time is the lower bound.

Building blocks

Insert Interval is built from two reusable bricks.

Interval merging

The core operation is the same one used in Merge Intervals: when two intervals overlap, combine them by taking the min of the starts and the max of the ends. The difference is that Merge Intervals requires sorting first, while Insert Interval gives you sorted input for free.

This building block shows up in:

• Merge Intervals (sort, then sweep and merge neighbors)
• Meeting Rooms II (track overlapping intervals with a heap)
• Non-overlapping Intervals (count removals using a greedy sweep)

Three-phase scan

When you need to insert an element into a sorted structure and handle collisions, splitting the scan into "before, collision, after" is a clean pattern. You avoid complex index arithmetic by letting three simple loops each handle one concern.

This decomposition is useful any time the input is sorted and you need to splice in new data while maintaining an invariant.

Edge cases

No overlap. If the new interval fits in a gap between existing intervals (or at the start or end), no merging happens. The second loop body never executes, and the new interval is inserted as-is.

New interval at the very start. intervals = [[3,5],[6,9]], newInterval = [1,2]. The first loop condition fails immediately (the first interval ends at 5, which is not less than 1... actually intervals[0][1] = 5 and newInterval[0] = 1, so 5 < 1 is false). The second loop checks 3 <= 2, which is false. So [1,2] gets appended first, then both existing intervals follow.

New interval at the very end. intervals = [[1,3],[6,9]], newInterval = [10,12]. The first loop adds both existing intervals (3 is less than 10, and 9 is less than 10). The second loop never runs. The new interval gets appended last.

New interval covers all existing intervals. intervals = [[2,3],[4,5],[6,7]], newInterval = [1,10]. The first loop adds nothing (no interval ends before 1). The second loop absorbs all three intervals into [1,10]. The third loop has nothing left. Result: [[1,10]].

Empty intervals list. If intervals is empty, all three loops are skipped and newInterval is the only element in the result.

From understanding to recall

You have seen the three-phase approach. The logic is clean: before, merge, after. But in an interview setting, the details matter. Is the "before" check strict less than or less-than-or-equal? Does the merge loop check the start or the end of the current interval? Which values get min and which get max?

These are small details that are easy to confuse under pressure. Reading the solution once is not enough to make it stick. The way to own this pattern is to practice writing it from scratch until the boundary conditions feel automatic.

Related posts

• Merge Intervals - The foundational interval merging pattern that Insert Interval builds on
• Meeting Rooms II - Uses sorted intervals with a heap to count maximum overlap

---

Visual Learner? See how sorting algorithms work with our Sorting Visualizations.