Skip to main content

57. Insert Interval

mediumAsked at Bloomberg

Insert 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 Alex Chen, 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^4
  • intervals[i].length == 2
  • 0 <= start_i <= end_i <= 10^5
  • intervals is sorted by start_i in ascending order.
  • newInterval.length == 2
  • 0 <= start <= end <= 10^5

Examples

Example 1

Input
intervals = [[1,3],[6,9]], newInterval = [2,5]
Output
[[1,5],[6,9]]

Example 2

Input
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output
[[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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Insert Interval and other Bloomberg interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →