Insert Interval

Find the boundary. Merge the middle. Leave the rest alone.

The common trap in the Insert Interval solution is treating the task as generic sorting followed by generic interval merging. That works, but it ignores the most valuable fact in the input: the existing intervals are already sorted and non-overlapping.

The better model is a boundary scan over an ordered timeline:

1. Copy intervals completely before the new interval.
2. Expand the new interval across every overlapping interval.
3. Append the untouched suffix.

The result is one linear pass after the input has already been sorted.

The contract and the one-pass answer

We have:

• An array of intervals sorted by start value.
• Existing intervals that do not overlap one another.
• A new interval to insert.
• Inclusive endpoints: [1, 3] and [3, 5] overlap because they share point 3.

The returned array must remain sorted and non-overlapping. The input does not need to be modified in place, so building a separate result list is the clearest implementation choice.

The key observation is that only the new interval can disturb the existing structure. Existing intervals are already in their final relative order. We do not need to reconsider every pair.

As we scan from left to right, every interval belongs to one of three regions:

• Before: safely left of the interval currently being merged.
• Overlapping: must be absorbed into that interval.
• After: safely right of the merged interval and everything that follows.

That gives us the entire algorithm before we write code:

copy the safe prefix
merge the contiguous overlap block
append the safe suffix

Recognize the three contiguous regions

Let the current existing interval be [current_start, current_end].

Let [merged_start, merged_end] represent the inserted interval as it expands during the scan.

1. Before

An existing interval is completely before the current merged interval when:

current_end < merged_start

The inequality is strict. If current_end == merged_start, the intervals touch and therefore overlap under the problem's inclusive endpoint rules.

A before-interval can be copied unchanged:

[current_start, current_end]

2. Overlapping

An interval overlaps the merged interval when the two ranges share at least one point. The equivalent condition is:

current_start <= merged_end
and
current_end >= merged_start

During the left-to-right scan, we have already removed the before case. Therefore, while the current interval starts no later than merged_end, it belongs to the overlap block:

current_start <= merged_end

Absorb it by expanding both boundaries:

merged_start = min(merged_start, current_start)
merged_end = max(merged_end, current_end)

The merged interval can grow to the left only when an existing interval begins earlier. It can grow to the right when an existing interval extends farther.

3. After

An existing interval is completely after the merged interval when:

current_start > merged_end

At this point the merged interval is finished. Because the input starts are sorted, every later interval begins at least as far right. No later interval can reach back and overlap the merged interval.

That is why the three regions are contiguous rather than scattered:

before, before, before,
overlap, overlap, overlap,
after, after, after

Once the scan reaches the first after-interval, the rest of the input is safe to copy without more comparisons.

Recognition rule: sorted order turns a collection of local comparisons into one irreversible boundary. Once an interval is definitely after the merged interval, the suffix is settled.

Derive the inclusive endpoint tests

Boundary comparisons cause most incorrect submissions here. Derive them from disjointness instead of memorizing a merge condition.

Two intervals are disjoint in exactly two directional ways:

• The current interval ends strictly before the merged interval starts.
• The current interval starts strictly after the merged interval ends.

So the tests are:

current_end < merged_start     # completely before
current_start > merged_end     # completely after

Everything else is overlap.

Consider:

[1, 3] and [3, 5]

They share the point 3, so they must merge into:

[1, 5]

If you write this instead:

current_end <= merged_start

you incorrectly classify touching intervals as separate. The same mistake appears at the right boundary if you use >= for the after test.

The phase-specific tests are preferable to repeatedly writing the full overlap expression. They match the algorithm's control flow:

1. Skip intervals that are definitely before.
2. Consume intervals that are not yet after.
3. Append everything remaining.

That is easier to inspect under interview pressure than a dense collection of overlapping cases.

Why sorting everything is the weaker baseline

A valid baseline is:

1. Append newInterval to intervals.
2. Sort all intervals by start.
3. Run the standard merge pass.

This works even when the input is unsorted, but it costs O(n log n) time because of the sort.

The supplied order gives us more information than that baseline uses. Re-sorting an already sorted interval list is rebuilding order that the problem has already paid to provide.

The preferred approach scans once in O(n). It is not merely shorter code. It is a better fit for the contract:

• Existing intervals already have a stable order.
• Existing intervals already do not overlap.
• Only one contiguous region can require merging.
• The suffix becomes permanently safe after the first after-interval.

There is a useful interview habit here: treat input constraints as algorithmic information. “Sorted” and “non-overlapping” are not decorative facts. They are invitations to eliminate work.

State and invariant: what the scan knows

The implementation needs only three pieces of state:

• i: the next existing interval to inspect.
• result: the finalized output prefix.
• merged: the inserted interval, expanded to include every overlap consumed so far.

The core invariant is:

Every interval already in result is finalized, sorted, non-overlapping, and strictly before merged. merged contains the inserted interval plus exactly the overlapping existing intervals consumed so far.

This invariant explains why each phase is safe.

Copying the prefix

While an interval ends before merged starts, it cannot overlap the inserted interval or any future expansion of it. Since the input is sorted, copying it preserves order.

The result prefix is now finalized.

Merging the middle

When an interval starts at or before merged_end, it overlaps the current merged interval. Replacing the boundaries with the minimum start and maximum end produces the smallest interval covering both.

Repeating this operation preserves the merge invariant. The merged interval always covers exactly the consumed overlap block.

Appending the suffix

When an interval starts after merged_end, the overlap block has ended. Since later starts cannot move backward, every remaining interval is also after merged.

Append merged once, then copy the suffix unchanged.

This establishes the required properties:

• Complete coverage: every input interval is either copied to the prefix, absorbed into merged, or copied to the suffix.
• Sorted output: prefix intervals come first, then merged, then the sorted suffix.
• No overlap: the prefix ends before merged starts, and the suffix starts after merged ends.
• Complete merging: every interval that touches or crosses merged is consumed before the merged interval is emitted.

The code is simple because the invariant carries the proof.

Dry-run: watch the moving interval

Use:

intervals = [[1,2], [3,5], [6,7], [8,10], [12,16]]
newInterval = [4,8]

The new interval begins in the middle of the list and touches [8,10] at endpoint 8.

Current interval	Classification	merged after processing	result
[1,2]	Before	[4,8]	[[1,2]]
[3,5]	Overlap	[3,8]	[[1,2]]
[6,7]	Overlap	[3,8]	[[1,2]]
[8,10]	Overlap at 8	[3,10]	[[1,2]]
[12,16]	After	[3,10]	[[1,2], [3,10]]

Finally, append the untouched suffix:

[[1,2], [3,10], [12,16]]

The important transition is [8,10]. Its start equals merged_end, so it belongs to the overlap block. That single equality is where many plausible implementations go wrong.

In Python, I prefer copying the new interval before using it as working state:

merged = newInterval[:]

That prevents the function from changing the caller's list while still giving us convenient mutable state. The algorithm does not require in-place modification, so there is little reason to introduce that side effect.

Implement the one-pass Python solution

class Solution:
    def insert(
        self,
        intervals: list[list[int]],
        newInterval: list[int],
    ) -> list[list[int]]:
        result = []
        i = 0
        n = len(intervals)

        # Copy intervals completely before the new interval.
        while i < n and intervals[i][1] < newInterval[0]:
            result.append(intervals[i])
            i += 1

        # Use a working copy so the caller's interval is not mutated.
        merged = newInterval[:]

        # Merge every interval that overlaps the working interval.
        while i < n and intervals[i][0] <= merged[1]:
            merged[0] = min(merged[0], intervals[i][0])
            merged[1] = max(merged[1], intervals[i][1])
            i += 1

        # Emit the merged interval exactly once.
        result.append(merged)

        # The remaining sorted suffix is already safe.
        while i < n:
            result.append(intervals[i])
            i += 1

        return result

Each loop corresponds directly to one obligation:

• The first loop preserves the safe prefix.
• The second loop performs the selective merge.
• The third loop preserves the safe suffix.

The second loop does not need to test intervals[i][1] >= merged[0]. Every interval that survived the first loop either overlaps merged or starts after its end. The loop condition selects the overlap side:

intervals[i][0] <= merged[1]

As merged[1] expands, an interval that was initially after the new interval can become part of the overlap block. That is why the condition must be checked against the moving boundary rather than the original newInterval[1].

Complexity, edge cases, and submission checks

Let n be the number of existing intervals.

Complexity

The index i only moves forward. Each existing interval is examined once and appended or merged once. There is no sorting.

Therefore:

• Time: O(n)
• Output space: O(n)
• Auxiliary space excluding the returned list: O(1)

The returned result can contain nearly every original interval plus the inserted interval, so the output itself naturally requires linear storage.

Edge cases to dry-run

Before submitting, test the boundaries rather than adding random examples:

• Empty input: [] with [2,5] returns [[2,5]].
• Insert before all intervals: the prefix loop copies nothing.
• Insert after all intervals: the merge loop consumes nothing, then the suffix is empty.
• Gap with no overlap: the new interval is emitted between the prefix and suffix.
• One overlap: verify both the minimum start and maximum end.
• Chain overlap: the merged end expands across several intervals.
• Touching on the left: [1,3] and [3,5] must merge.
• Touching on the right: [5,7] and [7,9] must merge.
• New interval contained by an existing interval: the existing boundaries should win.
• New interval containing several intervals: all of them should collapse into the new interval's expanded range.

A compact submission checklist:

1. Is the before test strict: current_end < merged_start?
2. Is the overlap test inclusive: current_start <= merged_end?
3. Is the merged interval appended exactly once?
4. Is the remaining suffix preserved?
5. Is the output still sorted and non-overlapping?

The transferable rule is simple: when a sorted, non-overlapping sequence receives one interval, identify the safe prefix, accumulate the contiguous overlap region, and preserve the safe suffix. Before coding, write the two strict disjointness predicates—and test equality at both boundaries.