Skip to main content

19. Insert Interval

mediumAsked at Figma

Insert a new interval into a sorted, non-overlapping list and merge overlaps. Figma uses this to probe how you'd merge bounding-box dirty regions during incremental render.

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

Problem

You are given a sorted array of non-overlapping intervals and a new interval. Insert the new interval, merging any overlaps, and return the resulting sorted, non-overlapping interval array.

Constraints

  • 0 <= intervals.length <= 10^4
  • intervals[i].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]]

Approaches

1. Push, sort, merge

Append the new interval and run the generic merge-intervals algorithm.

Time
O(n log n)
Space
O(n)
function insert(intervals, ni) {
  intervals.push(ni);
  intervals.sort((a, b) => a[0] - b[0]);
  const out = [];
  for (const i of intervals) {
    if (out.length && out.at(-1)[1] >= i[0]) out.at(-1)[1] = Math.max(out.at(-1)[1], i[1]);
    else out.push(i);
  }
  return out;
}

Tradeoff:

2. Three-phase linear pass

Walk once: copy intervals ending before newInterval, merge all that overlap by widening newInterval, then copy intervals starting after. Mirrors dirty-rect coalescing in a render pipeline.

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

Tradeoff:

Figma-specific tips

Figma rewards candidates who connect this to dirty-rect coalescing during partial canvas repaint — say the word 'dirty rect' explicitly during your walkthrough.

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 Figma interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →