Coding interview problems › Intervals

📅 Intervals Medium

Insert Interval

Insert Interval explained: add a new range to a sorted list of non-overlapping intervals in one O(n) pass with three phases, tested Python and a live visual.

Also searched as: insert into sorted intervals · insert and merge interval · add interval to non-overlapping list

📅

Try it live Free

Merge Intervals & Meeting Rooms

On the Merge Intervals timeline, drag a new interval across existing ones and watch the overlapping ones fuse into a single busy block.

Also useful: Binary Search

Open the playground →

The problem

You are given intervals that are sorted by start and do not overlap, plus one new interval. Insert the new interval and merge wherever needed so the result is still sorted and non-overlapping.

Inputintervals = [[1, 3], [6, 9]], new = [2, 5]
Output[[1, 5], [6, 9]]
Inputintervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], new = [4, 8]
Output[[1, 2], [3, 10], [12, 16]]

The key insight

Because the list is already sorted, it splits into three runs: intervals that end before the new one starts (copy them), intervals that overlap it (absorb them by widening the new interval), and intervals that start after it ends (copy them). No re-sorting is needed.

Brute force first: Appending the new interval and running the full Merge Intervals algorithm works but costs O(n log n) for a sort the input did not need.

Step-by-step approach

  1. Walk with index i. While intervals[i] ends before new starts, copy it to the output.
  2. While intervals[i] starts at or before new ends, widen new to cover it (min of starts, max of ends).
  3. Append the widened new.
  4. Copy all remaining intervals.
  5. Return the output.

Python solution

PYTHON 3tested
def insert(intervals, new_interval):
    out, i, n = [], 0, len(intervals)
    s, e = new_interval
    while i < n and intervals[i][1] < s:          # entirely before
        out.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= e:         # overlapping: absorb
        s = min(s, intervals[i][0])
        e = max(e, intervals[i][1])
        i += 1
    out.append([s, e])
    out.extend(intervals[i:])                      # entirely after
    return out

Complexity

TimeO(n)
SpaceO(n)

Each interval is visited once across the three loops. The output list holds up to n + 1 intervals.

Common mistakes

Frequently asked questions

What is the time and space complexity of Insert Interval?

O(n) time with one pass, and O(n) space for the new list.

Can binary search make Insert Interval faster?

Binary search can find where the overlapping run begins and ends in O(log n), but building the new list still costs O(n), so the overall bound does not change unless you use a mutable tree structure.

What if the input intervals are not sorted?

Then append the new interval and run the general Merge Intervals algorithm, which sorts first in O(n log n).

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Intervals Merge Intervals & Meeting Rooms lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.