Insert Interval – Solution & Complexity

Q: What is the time and space complexity of Insert Interval?

The optimal Insert Interval solution runs in `O(n)` time and `O(n)` space. A single linear pass copies intervals before the overlap, merges through it, then copies the rest.

Q: What is the most efficient way to solve Insert Interval?

A single linear pass copies intervals before the overlap, merges through it, then copies the rest. This gives `O(n)` time complexity, and is a classic arrays and intervals problem.

Q: How do you solve Insert Interval in Python, JavaScript, Java, Go & Rust?

We provide a worked Insert Interval solution in Python, JavaScript, Java, Go & Rust with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is Insert Interval an easy or hard interview question?

Insert Interval is generally rated **Medium**. It tests arrays and intervals, which are common coding-interview patterns.

Solution Walkthrough

1. Understand the Goal

intervals arrives pre-sorted and non-overlapping, so the only disorder in the whole array comes from inserting newInterval once.
Because of that guarantee, you never need a general sort or an O(n^2) overlap check — a single left-to-right scan is enough to find exactly where the new interval lands.

2. Choose the Core Pattern

Split the array into three contiguous phases relative to newInterval: intervals that end strictly before it starts, intervals that overlap it, and intervals that start strictly after it ends.
"Overlap" here includes endpoint-touching intervals like [1,2] and [2,3] — treat <=/>= (not strict </>) as the overlap test, since a merged [1,3] is still a single valid interval and keeping [1,2],[2,3] separate would be a needlessly fragmented answer.

3. Build the Algorithm

Phase 1: while the current interval's end is strictly less than the new interval's start, it can't overlap — copy it through unchanged.
Phase 2: while the current interval's start is <= the new interval's end, they touch or overlap — absorb it by taking the min of starts and max of ends, growing newInterval in place rather than emitting anything yet.
After phase 2 ends (or immediately if it never ran), emit the now-final merged interval exactly once.
Phase 3: copy every remaining interval through unchanged — by definition none of them can touch the merged interval, since the scan already passed the last one that could.

4. Check Edge Cases

Empty intervals: phases 1 and 3 run zero times and phase 2 also runs zero times, so the result is just [newInterval].
newInterval fits entirely before the first interval or after the last: it participates in zero merges and is emitted as its own entry in the correct position.
newInterval fully contains one or more existing intervals: the min/max absorption in phase 2 naturally swallows them without special-casing containment separately from partial overlap.

5. Final Solution and Complexity

Time complexity is O(n).
Space complexity is O(n).

def insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]:
    merged = []
    i = 0
    start, end = new_interval
    while i < len(intervals) and intervals[i][1] < start:
        merged.append(intervals[i])
        i += 1
    while i < len(intervals) and intervals[i][0] <= end:
        start = min(start, intervals[i][0])
        end = max(end, intervals[i][1])
        i += 1
    merged.append([start, end])
    while i < len(intervals):
        merged.append(intervals[i])
        i += 1
    return merged

Insert Interval – Solution & Complexity

Solution Walkthrough

1. Understand the Goal

2. Choose the Core Pattern

3. Build the Algorithm

4. Check Edge Cases

5. Final Solution and Complexity

FAQ

What is the time and space complexity of Insert Interval?

What is the most efficient way to solve Insert Interval?

How do you solve Insert Interval in Python, JavaScript, Java, Go & Rust?

Is Insert Interval an easy or hard interview question?

See also