Faangprep Logo
Log inStart free
Browse curriculum

Insert Interval

Insert a new interval into a sorted non-overlapping list.

MediumSolve on LeetCode

Problem Understanding

You are given an array of non-overlapping intervals sorted by start time. Your task is to insert a new interval into this list and merge any necessary intervals to maintain the sorted, non-overlapping property.

Example:

  • Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
  • Output: [[1,5],[6,9]]
  • Why? [2,5] overlaps with [1,3]. Combining them gives [1,5].

Algorithm Strategy

Since the list is already sorted, we can solve this in O(N) time using a single pass with three phases:

  1. Skip Left: Add all intervals that come strictly before the new interval (where end < newStart).
  2. Merge Overlaps: Use a while loop to process intervals that overlap with the new one (where start <= newEnd). Continuously update the new interval to [min(start), max(end)].
  3. Append Right: Once overlaps are resolved, add the (possibly expanded) new interval, then add all remaining intervals.

Interactive Visualization

Visualize the three-phase linear scan strategy.

Dry Run

Input: [[1,3], [6,9]], New: [2,5]

Step Interval Overlap? Action Result
1 [1,3] Yes (1 <= 5) Merge! New is [1, 5] []
2 [6,9] No (6 > 5) Stop merging. Add New [1,5]. Add Curr [6,9] [[1,5], [6,9]]
Final - - - [[1,5], [6,9]]

Edge Cases & Common Mistakes

  • New Interval is First/Last: e.g., Inserting [0,1] or [10,12] into [[2,5]].
  • No Overlaps: New interval fits perfectly in a gap.
  • Complete Overlap: New interval covers multiple existing ones [1,10] covers [2,3], [4,5].

Solution

Linear scan implementation.

Insert Interval Code
1var insert = function(intervals, newInterval) {
2    const result = [];
3    let i = 0;
4    const n = intervals.length;
5    
6    // 1. Left
7    while (i < n && intervals[i][1] < newInterval[0]) {
8        result.push(intervals[i++]);
9    }
10    
11    // 2. Merge
12    while (i < n && intervals[i][0] <= newInterval[1]) {
13        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
14        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
15        i++;
16    }
17    result.push(newInterval);
18    
19    // 3. Right
20    while (i < n) {
21        result.push(intervals[i++]);
22    }
23    
24    return result;
25};
Previous

Merge Intervals

Next

Non-overlapping Intervals

The approach, step by step

  1. Copy the intervals before it

    Add every interval whose end is less than the new interval’s start.

  2. Absorb overlaps

    While the next interval starts at or before the new interval’s end, widen the new interval to cover it.

  3. Place it and copy the rest

    Append the new interval, then every remaining interval.

Frequently asked questions

How does Insert Interval work in O(n)?

The list is already sorted, so one pass suffices: copy intervals that end before the new one starts, widen the new interval over every interval that overlaps it, append it, then copy the remaining intervals.

How do you know an interval overlaps the new one?

Once the intervals ending before the new one are copied, the next interval overlaps exactly when it starts no later than the new interval ends. Each overlap widens the new interval to the minimum start and maximum end.

Why not append the new interval and run Merge Intervals?

That works but sorts again for O(n log n). Insert Interval uses the fact that the input is already sorted and non-overlapping to finish in O(n).

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description