Insert Interval
Given a sorted list of non-overlapping intervals and a new interval, insert it and merge where necessary, returning the result still sorted and non-overlapping.
Open on LeetCode ↗Intuition
The input is already sorted and disjoint, so no sort is needed — one linear pass does it. Name the three phases before writing any conditionals: copy what ends before the new interval starts, absorb everything that touches it into one growing block, copy the rest. Two details decide correctness, and both are easy to get backwards: touching endpoints must count as overlapping, and the merged block's low end needs a min, because an existing interval may start earlier than the new one.
The input is already sorted, so three sequential passes suffice: copy everything strictly left of the new interval, absorb everything that touches it, then copy the rest. No sorting, no re-merging — the ordering does the work.
Approach
Copy everything that ends before the new interval starts
While intervals[i][1] < newInterval[0], the interval finishes before the new one starts, so append it unchanged. The comparison must be strict <: with <=, an interval merely touching at an endpoint gets copied instead of merged, and [1,3] with [3,5] comes out as two intervals when the answer is one.
Absorb every interval that overlaps
While intervals[i][0] <= hi, the interval starts at or before the current block's end, so it overlaps. Widen the block with lo = min(lo, start) and hi = max(hi, end). Taking the min on the low end matters — an existing interval may begin before the new one does. When the loop ends, push the single merged block.
Copy the rest
Everything remaining starts after the merged block ends, so it is appended untouched. Because the input was sorted, the output is sorted too, with no final sort required. One pass, O(n) time, and O(n) space for the output alone.
Solution & live demo
Common pitfalls
Using < for the overlap test
while i < n and intervals[i][0] < hi:
while i < n and intervals[i][0] <= hi:
Touching intervals like [1,3] and [3,5] must merge into [1,5]. The strict comparison treats them as disjoint and emits two adjacent intervals where one is expected.
Re-sorting and running the general merge
intervals.append(newInterval) intervals.sort() # merge all
while i < n and intervals[i][1] < newInterval[0]:
Correct but O(n log n) on already-sorted data. The three-phase walk is linear because it exploits the guarantee the problem hands you.
Not extending lo downward
hi = max(hi, intervals[i][1])
lo = min(lo, intervals[i][0]) hi = max(hi, intervals[i][1])
The first overlapping interval may start before the new one — inserting [4,8] into a list containing [3,5] yields [3,8]. Only tracking the upper bound truncates the merged result's left edge.
Edge cases
Both loops skip and the new interval is the entire answer.
Phase one copies nothing, phase two merges nothing, so it is placed first and the rest follow.
Phase one copies all, and the new interval lands at the end.
Phase two runs repeatedly, collapsing all of them into one block — the reason hi uses a running max.