Insert Interval: How to Explain the Three-Phase Scan in a Coding Interview

Author: 8f524892c3

02 November 2026

Views: 7

Insert Interval: How to Explain the Three-Phase Scan in a Coding Interview

Problem: you have a list of non-overlapping intervals sorted by start, and one new interval. Insert it and merge any overlaps.

The clean way to think about it is three phases in one left-to-right pass:

Phase 1 - intervals that end before the new one starts (interval.end < new.start). They cannot overlap, so copy them straight to the result.

Phase 2 - intervals that overlap the new one (interval.start <= new.end). Absorb each into the new interval: new.start = min(new.start, interval.start), new.end = max(new.end, interval.end). When the overlaps stop, append the merged new interval once.

Phase 3 - everything left starts after the new interval ends. Copy it as is.

Python:

def insert(intervals, new):
res, i, n = [], 0, len(intervals)
while i < n and intervals[i][1] < new[0]:
res.append(intervals[i]); i += 1
while i < n and intervals[i][0] <= new[1]:
new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]; i += 1
res.append(new)
res.extend(intervals[i:])
return res

Complexity: O(n) time, O(n) output space. No sorting needed because the input is already sorted, so do not reach for the general merge-intervals solution (O(n log n)) unless the interviewer changes the constraints.

Edge cases to mention out loud:
- empty list (the result is just [new])
- new interval before everything or after everything
- touching endpoints like [1,2] and [2,3]: confirm with the interviewer whether they count as overlapping (the code above merges them)
- new interval swallowing every existing interval

How to narrate it: say the three phases first, before writing code. Interviewers grade your plan as much as your syntax, and naming the phases makes the while-loop conditions obvious.

If you want a real-time practice partner while you rehearse explaining problems like this, I work on Linkjob AI, an AI coding interview assistant: https://www.linkjob.ai/coding-interview-copilot/ (disclosure: I am on the team).


Edit Code:

Please enter an edit code

Edit codes must be at least 20 characters

Share