57. Insert Interval
mediumAsked at BloombergInsert a new interval into a sorted list of non-overlapping intervals, merging as needed. Bloomberg uses this as the Merge Intervals follow-up — same shape but O(n) instead of O(n log n) because the input is pre-sorted.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Bloomberg loops.
- Glassdoor (2026-Q1)— Bloomberg SWE onsite reports list Insert Interval as the standard Merge Intervals follow-up.
- Blind (2025-11)— Bloomberg new-grad reports note this for fintech-team rounds.
Problem
You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the ith interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion.
Constraints
0 <= intervals.length <= 10^4intervals[i].length == 20 <= start_i <= end_i <= 10^5intervals is sorted by start_i in ascending order.newInterval.length == 20 <= start <= end <= 10^5
Examples
Example 1
intervals = [[1,3],[6,9]], newInterval = [2,5][[1,5],[6,9]]Example 2
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8][[1,2],[3,10],[12,16]]Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Approaches
1. Three-phase linear scan (optimal)
Phase 1: copy intervals ending before newInterval starts. Phase 2: merge all that overlap. Phase 3: copy the rest.
- Time
- O(n)
- Space
- O(n)
function insert(intervals, newInterval) {
const result = [];
let i = 0;
const n = intervals.length;
// Phase 1: before
while (i < n && intervals[i][1] < newInterval[0]) {
result.push(intervals[i]);
i++;
}
// Phase 2: merge overlapping
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.push(newInterval);
// Phase 3: after
while (i < n) {
result.push(intervals[i]);
i++;
}
return result;
}Tradeoff: Bloomberg's preferred answer. Three clean phases with one pass each, no sorting needed because the input is pre-sorted.
2. Push + re-sort + Merge Intervals
Append newInterval, sort, then run Merge Intervals.
- Time
- O(n log n)
- Space
- O(n)
function insertResort(intervals, newInterval) {
intervals.push(newInterval);
intervals.sort((a, b) => a[0] - b[0]);
const result = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = result[result.length - 1];
if (intervals[i][0] <= last[1]) last[1] = Math.max(last[1], intervals[i][1]);
else result.push(intervals[i]);
}
return result;
}Tradeoff: Reuses Merge Intervals but wastes the pre-sorted property. Bloomberg interviewers specifically grade whether you recognize O(n) is achievable.
Bloomberg-specific tips
Bloomberg interviewers want the three-phase O(n) solution. State 'because the input is pre-sorted, I can do this in one linear pass' BEFORE coding. The interviewer is grading whether you spot the O(n) opportunity vs reflexively sorting.
Common mistakes
- Re-sorting unnecessarily — input is already sorted.
- Using strict < instead of <= for overlap (touching intervals must merge).
- Forgetting Phase 3 — leftover intervals after newInterval end.
Follow-up questions
An interviewer at Bloomberg may pivot to one of these next:
- Merge Intervals (LC 56) — the unsorted-input version.
- Non-overlapping Intervals (LC 435) — remove the minimum to make non-overlapping.
- Meeting Rooms II (LC 253) — count max concurrent meetings.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is this O(n) and not O(n log n)?
Because intervals is sorted by start. We scan once: skip before, merge overlap, skip after. No sort needed.
Why mutate newInterval in place?
It's local — the caller passes a copy. Mutating saves the allocation; you can copy first if it makes the code clearer.
Free learning resources
Curated free links for this problem.