Inserting an interval
In one line
To insert a new interval into a sorted, disjoint list, copy everything that ends before it, absorb everything that overlaps it, then copy the rest: one pass, O(n).
What it is
Insert Interval gives you a list of non-overlapping intervals already sorted by start, plus one new interval. You must return the list with the new interval added and any overlaps merged, still sorted and disjoint.
Because the list is already sorted and clean, you do not need to sort again. The intervals split into three groups: those entirely to the left of the new one, those overlapping it, and those entirely to the right. Only the middle group changes.
Why interviewers ask
It checks whether you use the given structure (sorted, disjoint) to get O(n) instead of the O(n log n) 'append and re-merge' shortcut. It also tests precise boundary conditions: which comparison decides 'left', 'overlapping' and 'right'.
How it works
- 1Phase 1, left side: while the current interval ends before the new one starts (end < new.start), copy it to the output.
- 2Phase 2, overlap: while the current interval starts at or before the new one's end (start <= new.end), it overlaps. Grow the new interval to [min of starts, max of ends] and move on.
- 3Append the grown new interval.
- 4Phase 3, right side: copy every remaining interval; they all start after the new interval ends.
- 5Each interval is visited once, so it is O(n). Finding the first overlapping index can be done with binary search, but copying the output is still O(n).
Worked example · Insert [4, 8] into [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]
- Phase 1: [1, 2] ends at 2 < 4, copy it. [3, 5] ends at 5, not < 4, so phase 1 stops.
- Phase 2: [3, 5] starts at 3 <= 8: new becomes [min(4, 3), max(8, 5)] = [3, 8].
- [6, 7] starts at 6 <= 8: new stays [3, 8]. [8, 10] starts at 8 <= 8: new becomes [3, 10].
- [12, 16] starts at 12 > 10: phase 2 stops. Append [3, 10].
- Phase 3: copy [12, 16]. Result: [[1, 2], [3, 10], [12, 16]].
Picture it
Adding a new booking to a hotel room's sorted schedule: earlier bookings stay as they are, any bookings that clash with the new one get combined into one long block, and later bookings just shift along unchanged.
Reference code
def insert(intervals, new):
out, i, n = [], 0, len(intervals)
# 1. intervals that end before the new one starts
while i < n and intervals[i][1] < new[0]:
out.append(intervals[i])
i += 1
# 2. intervals that overlap the new one: absorb them
start, end = new
while i < n and intervals[i][0] <= end:
start = min(start, intervals[i][0])
end = max(end, intervals[i][1])
i += 1
out.append([start, end])
# 3. intervals that start after the new one ends
out.extend(intervals[i:])
return out
print(insert([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))
# [[1, 2], [3, 10], [12, 16]]The first loop uses end < new.start (strictly left), the second uses start <= end (overlapping or touching), and everything left over is strictly to the right. Change the comparisons if touching intervals should not merge.
Key patterns
Three-phase pass
When: Sorted, disjoint list plus one new interval
How: Copy left, absorb overlapping, copy right.
Binary search for the boundary
When: Very long lists and you mainly need to locate the position
How: Use bisect on starts or ends to find where the overlap begins; total work is still O(n) if you build a new list.
Remove an interval
When: Delete a range from a set of ranges
How: Same three phases; overlapping intervals are trimmed into at most a left piece and a right piece instead of merged.
Real-world use
Calendar updates
When you add an event, a calendar's free/busy summary only needs to update the busy blocks around the new event, not rebuild the whole day.
Memory and disk allocators
Allocators keep free regions as sorted, non-overlapping ranges; freeing a block inserts it and coalesces it with adjacent free regions so memory does not fragment.
Received-data tracking in TCP
Selective acknowledgement (SACK) tracks which byte ranges have arrived; each new segment is inserted into the list of received ranges and merged with neighbours.
In a project
A video platform tracks which seconds of a lecture each student has watched, to mark it complete at 90% coverage.
- Store each student's watched ranges as a sorted list of disjoint [start, end] seconds.
- Every time the player reports a watched segment, insert it with the three-phase pass so the list stays sorted and merged.
- Keep a running total of covered seconds, updated from the merged blocks that changed.
- Mark the lecture complete when covered seconds reach 90% of its length.
Impact: Rewatching the same minute no longer inflates progress, the stored list stays tiny (usually a handful of ranges), and each update is linear in that small list, so it scales to millions of progress events.
Trade-offs
Use it when
- The list is already sorted and disjoint
- You insert occasionally and can rebuild the list
- The list is short (per-user schedules, watched ranges)
Avoid it when
- Many inserts on a large list: use a balanced tree or sorted map keyed by start for O(log n + k) inserts
- The input is unsorted: sort and merge instead
Cost: O(n) time and O(n) space for the output. Re-sorting and merging instead would be O(n log n).
Common mistakes
- Appending the new interval and calling merge, which works but ignores the sorted input and costs O(n log n).
- Using <= in phase 1 or < in phase 2 inconsistently, so touching intervals are sometimes merged and sometimes not.
- Forgetting to append the new interval when nothing overlaps it, or when the list is empty.
- Updating only the end and not the start of the new interval (an overlapping interval may start earlier).
Interview questions
Quick revision
- Phase 1: end < new.start -> copy.
- Phase 2: start <= new.end -> new = [min starts, max ends].
- Append new, then copy the rest.
- O(n) time; no sorting needed.
- Always append the new interval, even with no overlaps.
- Many inserts? Use a sorted map / balanced tree.
Check yourself
1. Insert [2, 5] into [[1, 3], [6, 9]]. What is the result?
2. What is the time complexity of the three-phase insert?
3. Insert [4, 6] into [[1, 2], [8, 9]]. What happens in phase 2?
4. During phase 2, why update the start with min(start, interval.start)?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.