How Do You Solve the Insert Interval Problem?
Learn the three-phase O(n) approach to the insert interval problem and how to answer this common interview question well.
Expected Interview Answer
The insert interval problem gives you an already-sorted, non-overlapping list of intervals plus one new interval to add, and asks you to insert it while merging any overlaps, which can be done in a single O(n) linear pass without re-sorting since the list is already ordered.
Walk through the sorted list in three phases: first, copy every interval that ends strictly before the new interval starts (no overlap, comes before). Second, merge every interval that overlaps the new one by expanding the new interval's start to the minimum and end to the maximum across all overlapping intervals, then append the merged result once overlapping stops. Third, copy every remaining interval that starts strictly after the merged interval ends. Because the input is already sorted, no sorting step is needed, giving O(n) time and O(n) space for the output, which is asymptotically better than treating it as a generic merge-intervals problem that requires an O(n log n) sort.
- O(n) time, no re-sorting needed since input is already sorted
- Single linear pass with three clean phases
- O(n) output space for the result list
- Reuses the overlap-merging logic from general interval merging
AI Mentor Explanation
A season's fixture list is already sorted and has zero clashes, and now one new fixture request must be slotted in. The scheduler copies every existing fixture that finishes before the new one starts unchanged, then stretches the new fixture to swallow any fixture it overlaps, tracking the earliest start and latest finish among them, and finally copies every remaining fixture that starts after the (possibly stretched) new fixture ends. Because the original list was already ordered, there is no need to re-sort anything, so this single pass through the fixtures is enough.
Step-by-Step Explanation
Step 1
Copy non-overlapping intervals before
Append every interval that ends strictly before the new interval starts, unchanged.
Step 2
Merge all overlapping intervals
While an interval’s start is <= the new interval’s current end, expand the new interval to min(starts) and max(ends).
Step 3
Append the merged interval
Once overlap stops, push the (possibly expanded) new interval into the result once.
Step 4
Copy non-overlapping intervals after
Append every remaining interval that starts strictly after the merged interval ends, unchanged.
What Interviewer Expects
- Recognize the input is pre-sorted, so no sort step is needed — O(n) not O(n log n)
- Correctly identify the three phases (before, overlapping/merge, after)
- Handle edge cases: new interval overlapping none, all, or being fully contained
- State the O(n) time and O(n) space complexity
Common Mistakes
- Re-sorting the whole list unnecessarily, missing the O(n) opportunity
- Appending the new interval multiple times instead of merging it once
- Using strict < instead of <= when checking overlap boundaries
- Forgetting the trailing phase, dropping intervals that come after the new one
Best Answer (HR Friendly)
“Because the existing list is already sorted with no overlaps, I do not need to re-sort anything — I just walk through once, copy over intervals that come entirely before the new one, merge everything that overlaps into a single expanded interval, then copy over what comes after. It is an O(n) three-phase sweep instead of a full O(n log n) merge.”
Code Example
def insert_interval(intervals, new_interval):
result = []
i, n = 0, len(intervals)
new_start, new_end = new_interval
while i < n and intervals[i][1] < new_start:
result.append(intervals[i])
i += 1
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))
while i < n:
result.append(intervals[i])
i += 1
return result
print(insert_interval([(1, 3), (6, 9)], (2, 5)))
# [(1, 5), (6, 9)]Follow-up Questions
- How would the algorithm change if the existing list were not guaranteed sorted?
- How would you handle inserting many new intervals one after another efficiently?
- What edge cases should you test (new interval before all, after all, spanning all)?
- How is this related to the general merge intervals problem in terms of complexity?
MCQ Practice
1. Why can insert interval run in O(n) instead of O(n log n)?
Since the input is pre-sorted and non-overlapping, a single linear sweep suffices without re-sorting.
2. When merging overlapping intervals with the new interval, what should the merged start be?
The merged interval must start at the earliest point among everything it absorbs.
3. What is the space complexity of the insert interval algorithm?
The result list holds up to n+1 intervals, giving O(n) space.
Flash Cards
Why is insert interval O(n) instead of O(n log n)? — The input list is already sorted and non-overlapping, so no sort step is required.
How many phases does the insert interval sweep have? — Three: before (no overlap), merge (overlapping), after (no overlap).
How do you compute the merged interval’s bounds? — min of all overlapping starts (including the new interval) and max of all overlapping ends.
What is the time complexity of insert interval? — O(n), a single linear pass through the sorted list.