MediumArrayUpdated Sep 2026

57. Insert Interval

Asked at Oracle

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given a list of intervals intervals, where each interval is a pair [start, end]. The list is already sorted by start time, and no two intervals in it overlap. You are also given one extra interval newInterval = [start, end].

Your job is to put newInterval into the list so that the list stays sorted by start time and still has no overlapping intervals. If newInterval touches or overlaps any existing intervals, merge them all into one bigger interval. Two intervals overlap when they share at least one point, so [1,3] and [3,5] overlap because they both contain 3.

Return the final list of intervals. You do not have to change the input list in place — building and returning a new list is fine.

Insert [2,5] into a sorted list

intervals[1,3][6,9]01Existing intervals are sorted and do not overlap eachother.newInterval[2,5]0[2,5] shares points with [1,3], so they overlap.result[1,5][6,9]01Merged interval [1,5] comes first, then the untouched[6,9].
The new interval [2,5] overlaps [1,3], so those two must be merged into [1,5]; [6,9] is untouched.

Constraints

  • ●0 <= intervals.length <= 10^4
  • ●intervals[i].length == 2
  • ●0 <= starti <= endi <= 10^5
  • ●intervals is sorted by starti in ascending order
  • ●newInterval.length == 2
  • ●0 <= start <= end <= 10^5

Examples

Example 1
Inputintervals = [[1,3],[6,9]], newInterval = [2,5]
Output[[1,5],[6,9]]
Why[2,5] overlaps [1,3] because both contain points between 2 and 3. Merging them gives [1,5]. The interval [6,9] starts after 5, so it stays as is.
Example 2
Inputintervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output[[1,2],[3,10],[12,16]]
Why[4,8] overlaps [3,5], [6,7] and [8,10]. The union of all four intervals runs from 3 to 10, so they become one interval [3,10]. [1,2] ends before 4 and [12,16] starts after 10, so both are kept unchanged.

Asked At

1 companies
CompanyDifficulty
OracleMediumView all Oracle questions →

How to Think About It

1

Brute force: Append the new interval to the list, sort all intervals by start, then merge.

2

Identify all intervals that come entirely before the new interval (no overlap) and add them directly.

3

Find all intervals that overlap with the new interval and merge them into one combined interval.

4

Identify all intervals that come entirely after the new interval (no overlap) and add them directly.

5

Three-pass approach achieves O(n) time and O(n) space without sorting.

Optimal Approach

Three phases: First, add all intervals ending before the new interval starts. Second, merge all overlapping intervals by updating the new interval to span the union (taking min of starts and max of ends). Third, add the merged interval, then append all remaining intervals. This linear pass works because the input is already sorted.

Three phases in one pass

intervals[1,2][3,5][6,7][8,10][12,16]01234iPhase 1: [1,2] ends before 4, so it goes straight to theoutput.intervalsmerge into [3,10][1,2][3,5][6,7][8,10][12,16]01234Phase 2: each interval starting at or before 8 isabsorbed, so the new interval grows to [3,10].result[1,2][3,10][12,16]012Phase 3: push the merged interval, then copy [12,16]because it starts after 10.while end < newStart: copywhile start <= newEnd: mergepush new, then copy the rest
Skip intervals that end before the new start, absorb every overlapping interval, then copy the rest.
ComplexityTime O(n)Space O(n)One left-to-right pass over the intervals; the extra space is the output list, which can hold up to n + 1 intervals.

What Trips People Up in Real Interviews

1

Confirm the intervals are already sorted and non-overlapping before insertion.

2

Clarify the merge logic: the new merged interval spans from min(starts) to max(ends).

3

Handle edge cases: new interval at the beginning, at the end, or spanning the entire list.

4

Be careful with off-by-one when checking overlap (currEnd >= newStart && currStart <= newEnd).

5

Discuss why the three-pass solution is optimal compared to sort-then-merge.

Solution Code

O(n) time
def insert(intervals, newInterval):
    result = []
    i = 0
    n = len(intervals)
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    result.append(newInterval)
    while i < n:
        result.append(intervals[i])
        i += 1
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Insert Interval problem?

Given a set of non-overlapping intervals sorted by start time, insert a new interval and merge any overlapping intervals. Return the resulting set of intervals.

How do you solve Insert Interval?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Insert Interval?

Insert Interval is asked at Oracle. It is a medium difficulty problem.

What are common mistakes on Insert Interval?
  • Confirm the intervals are already sorted and non-overlapping before insertion.
  • Clarify the merge logic: the new merged interval spans from min(starts) to max(ends).
  • Handle edge cases: new interval at the beginning, at the end, or spanning the entire list.
  • Be careful with off-by-one when checking overlap (currEnd >= newStart && currStart <= newEnd).
  • Discuss why the three-pass solution is optimal compared to sort-then-merge.