LeetCode 57: Insert Interval

Problem Restatement

We are given a list of non-overlapping intervals sorted by start time.

Each interval has this form:

[start, end]

We are also given one new interval:

newInterval = [start, end]

We need to insert newInterval into the list so that the final list is still sorted and still has no overlapping intervals. If the new interval overlaps existing intervals, we merge them.

The input intervals are already sorted by start time and already non-overlapping. The official constraints allow 0 <= intervals.length <= 10^4.

Input and Output

Function shape:

def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
    ...

Examples

For:

intervals = [[1, 3], [6, 9]]
newInterval = [2, 5]

The new interval overlaps with [1, 3] because:

2 <= 3

So we merge them into:

[1, 5]

The interval [6, 9] does not overlap.

The answer is:

[[1, 5], [6, 9]]

For:

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

The new interval overlaps with:

[3, 5], [6, 7], [8, 10]

They merge into:

[3, 10]

The answer is:

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

First Thought: Add, Sort, and Merge

One simple approach is:

1. Add newInterval to intervals.
2. Sort all intervals by start time.
3. Use the same merge algorithm from LeetCode 56.

This works, but it ignores an important fact: the original intervals list is already sorted and non-overlapping.

Because of that, we can solve the problem in one pass without sorting again.

Key Insight

The existing intervals fall into three groups:

Because the input is sorted, these groups appear in this exact order.

So we can scan once:

1. Copy all intervals completely before the new interval.
2. Merge all intervals that overlap the new interval.
3. Append the merged new interval.
4. Copy all remaining intervals.

Algorithm

Use an index i.

First, append all intervals that end before the new interval starts:

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

Then merge all overlapping intervals:

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

Append the merged interval:

ans.append(newInterval)

Finally, append the rest:

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

Correctness

The input intervals are sorted and non-overlapping.

The first loop appends every interval whose end is smaller than the start of newInterval. Such intervals cannot overlap with newInterval, so they must appear before it in the result.

The second loop processes every interval whose start is less than or equal to the current end of newInterval. Each such interval overlaps the new interval, so merging is required. Updating the start with the smaller start and the end with the larger end preserves exactly the union of all overlapping intervals.

When the second loop ends, either all intervals were processed or the next interval starts after the merged interval ends. Therefore the merged interval no longer overlaps anything remaining, so appending it is correct.

All remaining intervals start after the merged interval ends. Since the original list was sorted and non-overlapping, they can be appended unchanged.

Thus the result is sorted, non-overlapping, and covers exactly the original intervals plus the inserted interval.

Complexity

No sorting is needed.

Implementation

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

        while i < n and intervals[i][1] < newInterval[0]:
            ans.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

        ans.append(newInterval)

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

        return ans

Code Explanation

We create the result list and start scanning from the first interval:

ans = []
i = 0
n = len(intervals)

First, copy all intervals that come completely before newInterval:

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

The condition uses <, not <=.

If an interval ends at the exact same point where newInterval starts, they overlap and must be merged.

Next, merge all overlapping intervals:

while i < n and intervals[i][0] <= newInterval[1]:

For every overlap, extend newInterval:

newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])

After all overlaps are merged, add the final merged interval:

ans.append(newInterval)

Then append everything after it:

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

Finally:

return ans

Testing

def run_tests():
    s = Solution()

    assert s.insert([[1, 3], [6, 9]], [2, 5]) == [
        [1, 5],
        [6, 9],
    ]

    assert s.insert(
        [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]],
        [4, 8],
    ) == [
        [1, 2],
        [3, 10],
        [12, 16],
    ]

    assert s.insert([], [5, 7]) == [[5, 7]]

    assert s.insert([[1, 2], [8, 10]], [3, 5]) == [
        [1, 2],
        [3, 5],
        [8, 10],
    ]

    assert s.insert([[3, 5], [7, 9]], [1, 2]) == [
        [1, 2],
        [3, 5],
        [7, 9],
    ]

    assert s.insert([[1, 2], [3, 5]], [6, 7]) == [
        [1, 2],
        [3, 5],
        [6, 7],
    ]

    assert s.insert([[1, 5]], [2, 3]) == [[1, 5]]

    assert s.insert([[1, 5]], [5, 7]) == [[1, 7]]

    print("all tests passed")

run_tests()