Skip to main content

57. Insert Interval

mediumAsked at Netflix

Given a sorted list of non-overlapping intervals and a new interval, insert it and merge as needed. Netflix asks this as the follow-up to Merge Intervals — they want you to leverage the pre-sorted input for a one-pass O(n) solution without re-sorting.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Netflix loops.

  • Glassdoor (2026-Q1)— Netflix L4/L5 onsite reports list Insert Interval as a follow-up after Merge Intervals.
  • Blind (2025-11)— Netflix SWE writeups describe a 3-phase walkthrough (before / overlap / after) as the expected narration.

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).

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. Append + merge

Push newInterval into the array, sort, then run Merge Intervals.

Time
O(n log n)
Space
O(n)
function insertNaive(intervals, newInterval) {
  const all = intervals.concat([newInterval]).sort((a, b) => a[0] - b[0]);
  const out = [];
  for (const [s, e] of all) {
    if (out.length === 0 || s > out[out.length - 1][1]) out.push([s, e]);
    else out[out.length - 1][1] = Math.max(out[out.length - 1][1], e);
  }
  return out;
}

Tradeoff: Works but wastes the pre-sorted input. Mention it as the baseline, then point out the O(n) version below.

2. Three-phase walk (optimal)

Phase 1: append all intervals strictly before newInterval. Phase 2: merge all intervals overlapping newInterval, expanding newInterval. Phase 3: append all intervals strictly after.

Time
O(n)
Space
O(n) output
function insert(intervals, newInterval) {
  const out = [];
  let i = 0;
  const n = intervals.length;
  while (i < n && intervals[i][1] < newInterval[0]) out.push(intervals[i++]);
  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++;
  }
  out.push(newInterval);
  while (i < n) out.push(intervals[i++]);
  return out;
}

Tradeoff: O(n), no sort. Three crisp phases — easy to write under interview pressure once you've practiced the 3-phase template.

Netflix-specific tips

Netflix interviewers want the three-phase narration BEFORE you write code. Say: 'I'll walk through three regions — strictly before, overlapping (merge into newInterval), strictly after.' If you start with the append-and-sort version, name the cost: 'I'm re-sorting an already-sorted input.' Then transition to the optimal.

Common mistakes

  • Using `<` instead of `<=` in the overlap-check (`intervals[i][0] <= newInterval[1]`) — incorrectly excludes touching intervals like [3,4] and [4,5].
  • Mutating intervals[i] instead of newInterval — works in JS but signals lazy variable management.
  • Forgetting Phase 3 (append remaining intervals) when newInterval is fully contained inside the input range.

Follow-up questions

An interviewer at Netflix may pivot to one of these next:

  • What if intervals were stored in a balanced BST? (O(log n) insertion plus O(k) merge for k overlapping.)
  • What if you needed to support deletion as well as insertion?
  • Merge Intervals (LC 56) — the unsorted-input variant.

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 the input is already sorted, you can find the insertion point in O(n) by linear scan — no sort needed. Each phase walks the array forward without backtracking.

Could a binary search make this faster?

Binary search finds the insertion point in O(log n), but you still have to walk and merge overlapping intervals which can be up to O(n) in the worst case. So overall complexity stays O(n).

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →