Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input intervals are already sorted by start time, and they do not overlap with each other.

That matters because the problem is not asking to rebuild the whole interval set from scratch. It is asking where one new interval fits into an already clean timeline.

Once the new interval is inserted, any intervals that touch or overlap it must be merged into one larger interval. Everything else should stay in the same order.

So the real task is:

  1. keep the intervals that end before the new interval starts
  2. merge every interval that overlaps the new interval
  3. keep the remaining intervals that start after the merged interval ends

The core insight

Because the original intervals are sorted and non-overlapping, the scan naturally falls into three contiguous regions.

First comes the prefix of intervals that are definitely before the new one. Those can be copied directly into the answer.

Next comes one consecutive block of overlapping intervals. There cannot be two separate overlap blocks, because if intervals are sorted and non-overlapping, once overlap starts, every overlapping interval must appear next to the previous one. That means the merged interval can be built by repeatedly expanding its start and end.

After that, all remaining intervals must lie completely to the right, so they can also be copied directly.

This turns what could look like a messy merge problem into one clean linear pass.

How to derive the optimal solution

A natural first idea is to append the new interval, sort everything, and then run the standard merge-intervals algorithm. That works, but it spends extra effort re-sorting data that is already sorted.

The key observation is that the existing intervals already give the order for free. The only interval whose position is unknown is the new one. So instead of re-sorting the whole list, it is better to walk left to right and ask a simpler question for each interval:

Is this interval fully before the new interval, overlapping it, or fully after it?

Those three cases are enough:

  • If current_end < new_start, the current interval is safely before the insertion point.
  • If current_start > new_end, the current interval is safely after the merged interval.
  • Otherwise, the two intervals overlap and should be merged by expanding the current [new_start, new_end].

Once the intervals move from the overlap case into the “after” case, they will stay there for the rest of the scan. That is why a single pass is sufficient.

Best approach

The optimal solution is a linear scan with one running merged interval.

It works in O(n) time because each interval is examined once. It uses O(n) extra space for the returned list, which is standard here because the answer itself may contain n + 1 intervals. There is no reason to do anything more complicated unless the problem changes and many insertions must be supported efficiently over time.

Python solution

from typing import List


class Solution:
    def insert(self, intervals: List[List[int]], new_interval: List[int]) -> List[List[int]]:
        """
        Insert one interval into a sorted, non-overlapping interval list.

        The algorithm scans the list once and handles three phases:
        1. intervals completely before the new interval
        2. intervals overlapping the new interval
        3. intervals completely after the merged interval
        """
        merged_intervals: List[List[int]] = []
        scan_index = 0
        merged_start, merged_end = new_interval

        # Copy every interval that ends before the new interval begins.
        while scan_index < len(intervals) and intervals[scan_index][1] < merged_start:
            merged_intervals.append(self._copy_interval(intervals[scan_index]))
            scan_index += 1

        # Merge every interval that overlaps the new interval.
        while scan_index < len(intervals) and intervals[scan_index][0] <= merged_end:
            current_start, current_end = intervals[scan_index]
            merged_start = min(merged_start, current_start)
            merged_end = max(merged_end, current_end)
            scan_index += 1

        merged_intervals.append([merged_start, merged_end])

        # Copy the remaining intervals unchanged.
        while scan_index < len(intervals):
            merged_intervals.append(self._copy_interval(intervals[scan_index]))
            scan_index += 1

        return merged_intervals

    @staticmethod
    def _copy_interval(interval: List[int]) -> List[int]:
        """Return a fresh interval list to avoid aliasing the input."""
        return [interval[0], interval[1]]

Why this works

The correctness comes from maintaining a simple invariant during the scan.

Before the overlap phase starts, every interval copied into the answer is guaranteed to end before the merged interval begins, so none of them can overlap anything that comes later.

During the overlap phase, the running interval [merged_start, merged_end] always represents the merge of the original new_interval and every interval seen so far that overlaps it. Expanding with min(start) and max(end) preserves that invariant.

After the overlap phase ends, the first interval that does not overlap must start strictly after merged_end. Because the list is sorted, every later interval will also start after merged_end, so the rest can be appended unchanged.

That covers all intervals exactly once, in order, and produces a sorted non-overlapping result.

Interview follow-ups

What if the input intervals are not sorted?

Then the linear scan is no longer valid, because the three-phase structure depends on sorted order. In that version, the clean approach is to append the new interval, sort all intervals by start time, and then run the standard merge pass. That costs O(n log n) time because sorting dominates. The merge itself is still linear. This is the right answer when the sorted-input guarantee is removed.

Can this be done in place?

Sometimes. If the interviewer only cares about reducing auxiliary allocations and allows mutation of the input, the intervals can be overwritten in the same array while a write pointer tracks the compacted result. That keeps extra working space close to O(1) beyond the returned structure, but it makes the code more delicate and less readable. In Python, returning a fresh result list is usually the better engineering choice unless the problem explicitly asks for in-place mutation.

What changes if touching endpoints should not merge?

The overlap condition changes. In the standard LeetCode version, [1, 5] and [5, 7] are considered overlapping because the intervals are closed, so the merge condition uses current_start <= merged_end. If the intervals were half-open or the interviewer said that touching intervals should remain separate, the condition would become current_start < merged_end instead. The rest of the algorithm stays the same, but that one comparison encodes the interval semantics and directly affects correctness.

What if there are many insert operations instead of just one?

For one insertion, the linear scan is optimal and simple. For many repeated insertions and queries, repeatedly scanning a flat list becomes expensive. At that point, the data structure should change. A balanced tree or interval tree can support faster updates and overlap searches, typically around O(log n) for structural operations plus the cost of handling the overlapping intervals found. The tradeoff is higher implementation complexity and more bookkeeping, so it only makes sense when the workload is dynamic rather than one-off.