How do you solve Insert Interval?

Iterate through intervals once. Append all intervals that end before the new interval starts. For intervals that overlap with the new interval, merge by updating the new interval's start and end to the min and max of overlapping intervals. Once all overlaps are merged, append the merged new interval and then append the remaining intervals. This approach guarantees O(n) time and O(n) space, preserving sorted order and merging efficiently.

Insert Interval

Q: What is the time complexity of Insert Interval?

O(n). The algorithm performs a single pass through the list of intervals, performing constant-time operations per interval, resulting in linear time complexity.

Q: What pattern does Insert Interval use?

The Pattern: Merge Intervals (Linear Scan with Boundary Updates) The Heuristic: When intervals are sorted and non-overlapping, insertions and merges can be done in a single pass by appending non-overlapping intervals, merging overlapping ones by updating boundaries, and then appending the rest, avoiding sorting and repeated scans.

Medium Merge Intervals

Problem

Given a list of non-overlapping intervals sorted by their start time, and a new interval, insert the new interval into the list and merge all overlapping intervals, returning the updated list of intervals sorted by start time.

0 ≤ intervals.length ≤ 10⁴
intervals[i].length == 2
0 ≤ intervals[i][0] ≤ intervals[i][1] ≤ 10⁵
intervals is sorted by intervals[i][0]
newInterval.length == 2
0 ≤ newInterval[0] ≤ newInterval[1] ≤ 10⁵

Example

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

Output: [[1,5],[6,9]]

The algorithm iterates through the intervals. The first interval [1,3] overlaps with the new interval [2,5], so they are merged into [1,5]. The second interval [6,9] does not overlap and is appended as is. The final result is [[1,5],[6,9]]. The critical moment is when the algorithm detects overlap and updates the new interval boundaries to merge intervals efficiently.

Approach

Straightforward Solution

A naive approach would insert the new interval and then sort and merge all intervals, resulting in O(n log n) time due to sorting and O(n) for merging. This is inefficient given the input is already sorted and non-overlapping.

Core Observation

Intervals are sorted and non-overlapping, so the new interval can be inserted by scanning from left to right, merging overlapping intervals as they appear. Overlapping intervals share a common range where the start of one is less than or equal to the end of the other.

Path to Optimal

Preview

The key recognition signals are 'sorted intervals' and 'merge overlapping intervals'. These indicate the Merge Intervals pattern because the problem can be solved in a single linear pass by leveraging the sorted order…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through intervals once. Append all intervals that end before the new interval starts…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm performs a single pass through the list of intervals, performing constant-time operations per interval, resulting in linear time complexity.

Space

O(n)

The output list stores all intervals including the merged new interval, requiring O(n) space proportional to the input size. No additional significant auxiliary space is used.

Pattern Spotlight

Merge Intervals (Linear Scan with Boundary Updates)

When intervals are sorted and non-overlapping, insertions and merges can be done in a single pass by appending non-overlapping intervals, merging overlapping ones by updating boundaries, and then appending the rest, avoiding sorting and repeated scans.

Solution

Python

1class Solution:
  def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
      res = []
4
      for i in range(len(intervals)):
          if newInterval[1] < intervals[i][0]:
              res.append(newInterval)
              return res + intervals[i:]
          elif newInterval[0] > intervals[i][1]:
              res.append(intervals[i])
          else:
              newInterval = [min(newInterval[0], intervals[i][0]), 
                             max(newInterval[1], intervals[i][1])]
      
      res.append(newInterval)
      return res

Step-by-Step Solution

Accumulate Non-Overlapping Intervals Before New Interval

3res = []
5for i in range(len(intervals)):
9    elif newInterval[0] > intervals[i][1]:
10        res.append(intervals[i])

Objective

To append all intervals that end before the new interval starts, as they do not overlap and can be safely added to the result.

Key Insight

Since intervals are sorted and non-overlapping, any interval whose end is less than the new interval's start cannot overlap with it. Appending these intervals directly preserves order and avoids unnecessary merging. This step effectively partitions the input into intervals before the new interval and those that may overlap or come after.

Interview Quick-Check

Core Logic

Append intervals that end before the new interval starts without modification, as they are guaranteed non-overlapping.

State & Boundaries

Use the condition `newInterval[1] < intervals[i][0]` to detect when the new interval should be inserted before the current interval.

Common Pitfalls & Bugs

Failing to append these intervals before merging can lead to incorrect ordering or missed intervals.

Merge Overlapping Intervals by Expanding New Interval Boundaries

To merge all intervals overlapping with the new interval by updating the new interval's start and end to cover the entire overlapping range.

Append Merged New Interval and Remaining Intervals

To add the merged new interval after processing all overlaps and then append any remaining intervals that come after it.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 6 Critical

if newInterval[1] < intervals[i][0]:

Check if the new interval ends before the current interval starts (no overlap).

This condition identifies the point where the new interval should be inserted before the current interval, as all subsequent intervals start after the new interval ends.

Line 9 Critical

elif newInterval[0] > intervals[i][1]:

Check if the new interval starts after the current interval ends (no overlap).

This condition identifies intervals that come entirely before the new interval and can be appended directly without merging.

Line 11 Critical

else:

Handle overlapping intervals by merging boundaries.

This else branch captures intervals that overlap with the new interval, requiring boundary updates to merge them into a single interval.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

Why does merging overlapping intervals by updating the new interval boundaries during the scan guarantee correctness and efficiency?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Insert Interval from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Insert Interval drill

or drill a free problem

1	`class Solution:`
2	`def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:`
3	`res = []`
4
5	`for i in range(len(intervals)):`
6	`if newInterval[1] < intervals[i][0]:`
7	`res.append(newInterval)`
8	`return res + intervals[i:]`
9	`elif newInterval[0] > intervals[i][1]:`
10	`res.append(intervals[i])`
11	`else:`
12	`newInterval = [min(newInterval[0], intervals[i][0]),`
13	`max(newInterval[1], intervals[i][1])]`
14
15	`res.append(newInterval)`
16	`return res`

3	`res = []`
5	`for i in range(len(intervals)):`
9	`elif newInterval[0] > intervals[i][1]:`
10	`res.append(intervals[i])`