57. Insert Interval

mediumAsked at Canva

Insert a new interval into a sorted, non-overlapping list and merge as needed — Canva's animation timeline must splice new keyframe ranges into an existing schedule without disruption, making this a direct analogue to production code.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

Problem

You are given an array of non-overlapping intervals sorted in ascending order by start time, and a single new interval. Insert the new interval, merging with any overlapping existing intervals, and return the resulting list of non-overlapping intervals still sorted by start time.

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

Examples

Example 1

Input

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

Output

[[1,5],[6,9]]

Explanation: New interval [2,5] overlaps [1,3] and merges to [1,5].

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: [4,8] overlaps [3,5],[6,7],[8,10] and merges them into [3,10].

Approaches

1. Linear scan with three phases

Walk the sorted list in three phases: copy intervals that end before the new one starts, merge all overlapping intervals into the new one, then copy the remaining intervals.

Time: O(n)
Space: O(n)

function insert(intervals, newInterval) {
  const result = [];
  let i = 0;
  const n = intervals.length;
  // Phase 1: intervals that end before newInterval starts
  while (i < n && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }
  // Phase 2: merge overlapping intervals
  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: remaining intervals
  while (i < n) {
    result.push(intervals[i]);
    i++;
  }
  return result;
}

Tradeoff:

2. Binary search + linear merge

Use binary search to find the insertion point, then merge the affected interval range — same O(n) overall due to the array copy, but log-n fewer comparisons in practice.

Time: O(n)
Space: O(n)

function insert(intervals, newInterval) {
  const result = [];
  let [newStart, newEnd] = newInterval;
  let inserted = false;
  for (const [start, end] of intervals) {
    if (end < newStart) {
      result.push([start, end]);
    } else if (start > newEnd) {
      if (!inserted) {
        result.push([newStart, newEnd]);
        inserted = true;
      }
      result.push([start, end]);
    } else {
      newStart = Math.min(newStart, start);
      newEnd = Math.max(newEnd, end);
    }
  }
  if (!inserted) result.push([newStart, newEnd]);
  return result;
}

Tradeoff:

Canva-specific tips

Canva interviewers like this over plain Merge Intervals because it tests whether you can handle an empty input array (return [[newInterval]]) and a newInterval that doesn't overlap anything (insert at the right position). Walk through the boundary conditions before coding: what happens when newInterval comes entirely before all existing intervals? Entirely after? The three-phase linear scan is the cleanest approach to explain aloud and maps directly to how a timeline editor would splice a new clip into a sorted track list.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →