Insert Interval

You are given a list intervals of closed intervals [start, end] that do not overlap one another and are sorted by start. You are also given one more interval, newInterval.

Insert newInterval into the list and return the result, which must again be sorted by start and free of overlaps. Wherever the new interval overlaps existing ones, merge them all into a single interval covering their union.

Intervals are closed, so two intervals that merely share an endpoint, like [1,3] and [3,5], overlap and must be merged into [1,5]. You may build and return a new list.

Example 1

Example 2

Example 3

Constraints

• 0 <= intervals.length <= 104
• intervals[i].length == 2 and newInterval.length == 2
• 0 <= start <= end <= 105
• intervals is sorted by start and contains no overlapping intervals.

Pattern Path · Intervals & Greedy · problem 110 of 169

Start simple

Append the new interval, sort everything by start, and run a general merge-intervals pass: O(n log n) time, ignoring that the input was already sorted.

The key idea

Because the existing intervals are sorted and disjoint, they fall into three consecutive groups relative to newInterval = [s, e]:

• Entirely before: their end is less than s. They cannot touch the new interval, so copy them as they are.
• Overlapping: their start is at most e (and their end is at least s). Each one shares at least a point with the growing merged interval, so fold it in: s = min(s, start), e = max(e, end).
• Entirely after: their start is greater than e. Append the merged [s, e] once, then copy the rest.

The groups are contiguous because the list is sorted: once an interval starts after e, every later one does too, and widening only happens with intervals that already overlap. Using strict comparisons (end < s, start > e) for the outer groups makes shared endpoints count as overlaps.

One pass, each interval handled once, gives linear time.

Complexity

• Time: O(n)
• Space: O(n) for the output

Python

class Solution:
    def insert(self, intervals, newInterval):
        s, e = newInterval
        result = []
        i, n = 0, len(intervals)

        # 1. Intervals that end before the new one starts.
        while i < n and intervals[i][1] < s:
            result.append(intervals[i])
            i += 1

        # 2. Intervals that overlap the new one: merge them in.
        while i < n and intervals[i][0] <= e:
            s = min(s, intervals[i][0])
            e = max(e, intervals[i][1])
            i += 1
        result.append([s, e])

        # 3. Intervals that start after the merged one ends.
        result.extend(intervals[i:])
        return result

JavaScript

var insert = function(intervals, newInterval) {
  let [s, e] = newInterval;
  const result = [];
  let i = 0;
  const n = intervals.length;

  // 1. Intervals that end before the new one starts.
  while (i < n && intervals[i][1] < s) {
    result.push(intervals[i]);
    i++;
  }

  // 2. Intervals that overlap the new one: merge them in.
  while (i < n && intervals[i][0] <= e) {
    s = Math.min(s, intervals[i][0]);
    e = Math.max(e, intervals[i][1]);
    i++;
  }
  result.push([s, e]);

  // 3. Intervals that start after the merged one ends.
  while (i < n) result.push(intervals[i++]);
  return result;
};

What the interviewer is checking

It tests careful case analysis on intervals: identifying the before, overlapping and after groups, and getting boundary conditions such as touching endpoints exactly right.

Mistakes to avoid

• Using <= instead of < for the "before" test, so touching intervals are not merged.
• Forgetting to append the merged interval when it belongs at the very end (or when the input is empty).
• Merging only with the first overlapping interval instead of all of them.
• Mutating the input while iterating over it.

Follow-ups to expect

• How fast can you find where the overlap starts? (Binary search, but output is still O(n).)
• What if intervals arrive one at a time? (Balanced tree or sorted map keyed by start.)
• How would you remove an interval instead? (Split overlapping ones around it.)

In real software

Calendar apps adding a meeting to a list of busy blocks, and memory allocators merging a freed block with its free neighbours, perform exactly this insert-and-merge.

Practice next