Insert Interval

Table of Contents +

Insert Interval looks scary at first. You have a list of time ranges that already sit in order. Then someone hands you one more range and says “fit this in.” The tricky part is that the new range might touch or cover some of the old ones. So this question really tests if you can handle overlaps without getting lost.

🎯 The Problem

You get sorted intervals, and you must fit one more in. Here are the rules.

  • The intervals are already sorted by their start.
  • An interval is a pair of numbers, a start and an end. Think of it as a busy block of time.
  • You are given one new interval to add.
  • Return the list, still sorted, with any overlapping blocks joined into one.

Two blocks overlap when they share even a moment. So if one block ends at 5 and the next starts at 3, they touch. They must become a single block.

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


Explanation: [2, 5] overlaps with [1, 3], so they merge into [1, 5].
The block [6, 9] does not overlap, so it stays the same.

Here is the same example drawn on a number line. You can see how [1, 3] and [2, 5] share the spot around 2 and 3, so they join.

1---3 (old)

2-----5 (new)

6----9 (old)

overlap: join into 1---5

no overlap: stays 6---9

You can assume the list stays sorted by start the whole time.

🐢 Approach 1: Rebuild From Scratch (Brute Force)

The idea in one line: add the new interval, sort everything, then merge overlaps.

The idea:

  • Push the new interval into the list.
  • Sort the whole list by start.
  • Walk it and merge any blocks that overlap.

How it works:

  • You treat it like a fresh “merge all intervals” problem.
  • It does give the right answer.

Why it is weak:

  • The list was already sorted. You sort it again for nothing.
  • Sorting costs O(n log n) time.
  • That is wasted work the input already did for you.

Here is the append-then-sort code for that idea:

insert_interval_brute_force.py
def insert(intervals, new_interval):
    intervals = intervals + [new_interval]
    intervals.sort()


    merged = []
    for start, end in intervals:
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return merged

⚡ Approach 2: Three Phases In One Pass (Best)

The idea in one line: because the list is already sorted, walk it once in three clear phases.

Phase one, before:

  • Blocks that end before the new interval starts.
  • They sit fully to the left. They cannot overlap.
  • Copy them straight into the answer.

Phase two, the merge zone:

  • Blocks that touch the new interval.
  • A block touches when its start is not past the new end.
  • Pull the new start back to the smallest start you see. Push the new end forward to the largest end.
  • When the zone ends, drop the stretched new interval into the answer.

Phase three, after:

  • Blocks that start after the new interval fully ends.
  • They sit to the right. They cannot overlap.
  • Copy them straight in too.

Why it is fast:

  • One pass. No sort.
  • That makes it O(n) time. Much faster than rebuilding.

Here is the flow of those three phases as the pass moves left to right.

Start: walk sorted list

Phase 1: block ends before new start, copy as is

Phase 2: block overlaps, stretch new start and end

Phase 3: block starts after new end, copy as is

Done: return answer

Steps to Solve

  1. Make an empty result list and a pointer i at the front of the input.
  2. While the current block ends before the new interval starts, copy it to the result and move i forward.
  3. While the current block overlaps the new interval, shrink the new start to the smaller start and grow the new end to the larger end, then move i forward.
  4. Add the now stretched new interval to the result.
  5. Copy every remaining block to the result, because they all sit to the right.
  6. Return the result.

This Python version uses a plain list and the same three-phase walk.

insert_interval.py
def insert_interval(intervals, new_interval):
    result = []
    n = len(intervals)
    i = 0
    new_start, new_end = new_interval


    # Phase 1: blocks fully before the new interval
    while i < n and intervals[i][1] < new_start:
        result.append(intervals[i])
        i += 1


    # Phase 2: overlapping blocks, stretch the new interval
    while i < n and intervals[i][0] <= new_end:
        new_start = min(new_start, intervals[i][0])
        new_end = max(new_end, intervals[i][1])
        i += 1
    result.append([new_start, new_end])


    # Phase 3: blocks fully after the new interval
    while i < n:
        result.append(intervals[i])
        i += 1


    return result




intervals = [[1, 3], [6, 9]]
new_interval = [2, 5]
print(insert_interval(intervals, new_interval))

The output of the above code will be:

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

Now let us walk through the Python version line by line and see why each part is written this way.

def insert_interval(intervals, new_interval):
    result = []
    n = len(intervals)
    i = 0
    new_start, new_end = new_interval

We start with an empty result list. The pointer i tracks where we are in the input. We unpack the new interval into new_start and new_end because we will stretch these two values, and we do not want to keep indexing into a list.

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

This is phase one. The check intervals[i][1] < new_start reads as “this block ends before the new one starts.” If that is true the block sits fully to the left, so it can never overlap. We copy it and move on.

    while i < n and intervals[i][0] <= new_end:
        new_start = min(new_start, intervals[i][0])
        new_end = max(new_end, intervals[i][1])
        i += 1
    result.append([new_start, new_end])

This is phase two, the merge zone. The check intervals[i][0] <= new_end reads as “this block starts before the new one ends.” We already passed every block that ends too early, so any block that starts in time must overlap. We pull new_start back and push new_end forward. After the loop we drop the stretched interval in once.

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

This is phase three. Everything left starts after the new interval ends, so we copy it all and return. Three simple loops, one pass, no sort.

⏱️ Time and Space Complexity

The rebuild way adds the interval then sorts again, so it pays O(n log n) for the sort. The three-phase way walks the sorted list one time, so it is O(n). Both need room for the answer, which holds about n blocks. So the real win is dropping the sort and getting down to O(n) time.

Approach Time Complexity Space Complexity
Add then re-sort and merge O(n log n) O(n)
Three-phase single pass O(n) O(n)

Tip

The key insight to say out loud is that the input is already sorted. That single fact lets you skip the sort and split the work into before, overlap, and after.

🧩 Key Takeaways

  • ✅ The input is already sorted, so you never need to sort it again.
  • ✅ Split the walk into three phases: before the new interval, overlapping it, and after it.
  • ✅ Two blocks overlap when one starts before the other ends.
  • ✅ In the merge zone, keep shrinking the start and growing the end of the new interval.
  • ✅ One pass means O(n) time, which beats the O(n log n) rebuild.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Why can we skip sorting in the optimal Insert Interval solution?

    Why: The input list comes sorted by start, so we can walk it once and split the work into three phases without sorting again.

  2. 2

    When does a block overlap the new interval in phase two?

    Why: After skipping blocks that end too early, any block whose start is not past the new end must overlap.

  3. 3

    Inside the merge zone, how do we grow the new interval?

    Why: We pull the start back with min and push the end forward with max, so the merged block covers every overlapping piece.

  4. 4

    What is the time complexity of the three-phase single pass?

    Why: We touch each interval once across the three loops, so the work is linear, O(n).

Score: 0 / 4

🚀 What’s Next?

Previous UTF-8 Validation Next Merge Intervals