Developers

Insert Interval

MediumIntervalsGrade CAlso known as LeetCode 57

You are given a list intervals of non-overlapping intervals [start, end], sorted by start, and a new interval newInterval = [start, end]. Insert newInterval into the list so that the list stays sorted and has no overlapping intervals, merging any intervals that overlap it. Return the resulting list.

Intervals that share an endpoint, such as [1, 3] and [3, 5], overlap and are merged into [1, 5].

Examples

intervals
intervals, drawn on a number line: [1, 3], [6, 9], [2, 5] (highlighted).123456789[1, 3][6, 9][2, 5]

The highlighted bar is newInterval.

Input intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
Output [[1, 5], [6, 9]]
intervals
intervals, drawn on a number line: [1, 2], [3, 5], [6, 7], [8, 10], [12, 16], [4, 8] (highlighted).246810121416[1, 2][3, 5][6, 7][8, 10][12, 16][4, 8]

The highlighted bar is newInterval.

Input intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
Output [[1, 2], [3, 10], [12, 16]]
intervals
intervals, drawn on a number line: [5, 7] (highlighted).567[5, 7]

The highlighted bar is newInterval.

Input intervals = [], newInterval = [5, 7]
Output [[5, 7]]

Constraints

  • 0 <= intervals.length <= 10,000
  • intervals[i] = [start, end] with 0 <= start <= end <= 100,000
  • intervals is sorted by start and its intervals do not overlap
  • newInterval = [start, end] with 0 <= start <= end <= 100,000

Stuck? Take one hint at a time

Common mistakes
  • Treating touching intervals as separate: [1, 3] and [3, 5] overlap here, so the condition is "starts at or before the end", not "starts before".
  • Using "ends at or before" in the first loop, which would copy an interval that touches the new interval instead of merging it.
  • Adding the merged interval inside the second loop, once per absorbed interval, instead of once after it.
  • Taking the new start and end from the first overlapping interval only, instead of the minimum start and the maximum end across all of them.
  • Sorting by end instead of start in the sort based version.
Questions an interviewer may ask next
  • Remove an interval from the list instead of inserting one. (Intervals that overlap it are cut, and may split in two.)
  • The intervals are stored in a balanced tree or skip list. Which operation gives O(log n + k) for inserting, where k is the number merged?
  • Insert many new intervals one after another. What data structure makes each insertion cheap? (An ordered map keyed by start.)
  • Count how many intervals the insertion merged, without building the answer.

How often this is reported

Commonly reported across 1 of 25 tracked companies
1/25

Grade C: Reported in one source, or backed mainly by volume of reports. This reflects what candidates report, not a guarantee of what any company will ask.